1078
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() //#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int _i = 0; _i < _n; _i++) #define FORI(_i, _k, _n) for(int _i = _k; _i < _n; _i++) #define INPUT_FILE "xo.in" #define OUTPUT_FILE "xo.out" vi res; int m[500][500] = {0}; int R[500] = {0}; int M[500] = {0}; int n; int dfs(int v) { int ret = 0; int rr = 0; if(R[v] > 0) return R[v]; FOR(i,n) { if(m[v][i] == 1) { rr = dfs(i); if(rr > ret) { M[v] = i; ret = rr; } } } R[v] = ret + 1; return R[v]; } void print(int v) { if(R[v] > 1) print(M[v]); res.pb(v+1); } int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else // freopen(INPUT_FILE, "r", stdin); // freopen(OUTPUT_FILE, "w", stdout); #endif vector< ii > v; cin >> n; FOR(i,n) { int x,y; cin >> x >> y; v.pb(make_pair(min(x,y), max(x,y))); } FOR(i,n) { FOR(j,n) { if(i == j) continue; if((v[i].first > v[j].first) && (v[i].second < v[j].second)) m[i][j] = 1; } } FOR(i,n) dfs(i); int p = 0; FORI(i,1,n) { if(R[i] > R[p]) p = i; } print(p); reverse(res.begin(), res.end()); cout << sz(res) << endl; FOR(i,sz(res)) cout << res[i] << " "; return 0; }
page revision: 0, last edited: 22 Apr 2007 11:02