Codeforces Global Round 3 : D. Dirty Deeds Done Dirt Cheap

いまいち何がしたいかわからない問題。
https://codeforces.com/contest/1148/problem/D

問題

数列がGoodであるとは、隣接要素同士の大小関係を並べると、上昇・下降が交互に現れることを意味する。
（上昇と下降どちらが先に来てもよい）

数値の対(A[i],B[i])の列が与えられる。
この列の部分集合を選んだ上で任意の順に並べ、その後数値のを対をflatに並べなおしたとき、その数列がGoodとなる最長のものを求めよ。

解法

解に含む要素は、(A[i]＜B[i])となるものだけか、(A[i]＞B[i])の物だけで構築しなければならない。
逆に同種の物はすべて解に含められる。

例えば前者となる要素をすべて並べることを考える。
その場合A[i]を降順にすればよい。A[i]＞A[j]ならば、A[i]＜B[i]＞A[j]＜B[j]なので全要素Goodとなるように並べられる。

int N;
int A[303030],B[303030];
int F[303030];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<int,int>> V[2];
	FOR(i,N) {
		cin>>A[i]>>B[i];
		
		if(A[i]<B[i]) {
			V[0].push_back({-A[i],i});
		}
		else {
			V[1].push_back({A[i],i});
		}
	}
	
	sort(ALL(V[0]));
	sort(ALL(V[1]));
	if(V[0].size()<V[1].size()) swap(V[0],V[1]);
	_P("%d\n",V[0].size());
	FORR(v,V[0]) _P("%d ",v.second+1);
	
	
}

まとめ

Div2 D相当にしても簡単な気がする。Div2 Cぐらい？