oj.uz

Submission #26461

# Submission time Handle Problem Language Result Execution time Memory
26461 2017-07-01T05:30:12 Z zscoder Carnival (CEOI14_carnival) C++14
100 / 100
 9 ms 2032 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

const bool DEBUG = 0;
int a[1001];
int query(vi &vec)
{
	if(vec.empty()) return 0;
	if(vec.size()==1) return 1;
	cout<<vec.size()<<' ';
	for(int i=0;i<vec.size();i++)
	{
		cout<<vec[i]+1;
		if(i+1<vec.size()) cout<<' ';
	}
	cout<<'\n';
	fflush(stdout);
	int x; 
	if(!DEBUG) cin>>x; 
	else 
	{
		set<int> s;
		for(int i=0;i<vec.size();i++) s.insert(a[vec[i]]);		
		x=s.size();
	}
	return x;
}

pair<vi,vi> solve2(vi &L, vi &R, vi &oril, vi &orir)
{
	assert(L.size()==R.size());
	if(L.empty()) return {{},{}};
	if(L.size()==1) return {{0},{0}};
	/*
	cerr<<"SOLVE 2 :\n";
	for(int i=0;i<L.size();i++) cerr<<L[i]<<' ';
	cerr<<'\n';
	for(int i=0;i<R.size();i++) cerr<<R[i]<<' ';
	cerr<<'\n';
	for(int i=0;i<oril.size();i++) cerr<<oril[i]<<' ';
	cerr<<'\n';
	for(int i=0;i<orir.size();i++) cerr<<orir[i]<<' ';
	cerr<<'\n';
	for(int i=0;i<oril.size();i++) cerr<<a[oril[i]]<<' ';
	cerr<<'\n';
	for(int i=0;i<orir.size();i++) cerr<<a[orir[i]]<<' ';
	cerr<<'\n'<<'\n';
	*/
	int n = L.size();
	int col = n/2;
	vi vtmp;
	for(int i = 0; i < n/2; i++)
	{
		vtmp.pb(oril[i]);
	}
	vi Lidx,Ridx;
	for(int i = 0; i < orir.size(); i++)
	{
		vtmp.pb(orir[i]);
		int col2 = query(vtmp);
		if(col2>col)
		{
			Ridx.pb(i);
			//cerr<<"R "<<i<<'\n';
		}
		else
		{
			Lidx.pb(i);
			//cerr<<"L "<<i<<'\n';
		}
		vtmp.pop_back();
	}
	vi filler(n);
	vi perm(n);
	vi t1,t2;
	{
		vi l,r,ori1,ori2;
		for(int i=0;i<Lidx.size();i++)
		{
			int idx = Lidx[i];
			l.pb(L[i]);
			r.pb(R[idx]);
			ori1.pb(oril[i]);
			ori2.pb(orir[idx]);
		}
		t1=solve2(l,r,ori1,ori2).se;
	}
	{
		vi l,r,ori1,ori2;
		for(int i=0;i<Ridx.size();i++)
		{
			int idx = Ridx[i];
			l.pb(L[i+n/2]);
			r.pb(R[idx]);
			ori1.pb(oril[i+n/2]);
			ori2.pb(orir[idx]);
		}
		t2=solve2(l,r,ori1,ori2).se;
	}
	for(int i = 0; i < Lidx.size(); i++)
	{
		filler[i] = i;
		perm[Lidx[i]] = t1[i];
	}
	for(int i = 0; i < Ridx.size(); i++)
	{
		filler[i+n/2] = i+n/2;
		perm[Ridx[i]] = t2[i]+n/2;
	}
	/*
	for(int i=0;i<filler.size();i++)
	{
		cerr<<filler[i]<<' ';
	}
	cerr<<'\n';
	for(int i=0;i<perm.size();i++)
	{
		cerr<<perm[i]<<' ';
	}
	cerr<<'\n';
	*/
	return mp(filler,perm);
}

vi solve(vi &vec)
{
	if(vec.empty()) return vi();
	if(vec.size()==1) return {0};
	if(vec.size()==2)
	{
		int tmp = query(vec);
		if(tmp==2) return {0,1};
		else return {0,0};
	}
	/*
	for(int i = 0; i < vec.size(); i++)
	{
		cerr<<vec[i]<<' ';
	}
	cerr<<'\n';
	*/
	//random_shuffle(vec.begin(),vec.end());
	vi L,R;
	int n=vec.size();
	for(int i=0;i<n/2;i++)
	{
		L.pb(vec[i]);
	}
	for(int i=n/2;i<n;i++)
	{
		R.pb(vec[i]);
	}
	int col = query(vec);
	//cerr<<"COL "<<col<<' '<<n<<'\n';
	if(col==1)
	{
		vi ans;
		for(int i=0;i<n;i++) ans.pb(0);
		return ans;
	}
	if(col==int(vec.size()))
	{
		vi ans;
		for(int i=0;i<n;i++) ans.pb(i);
		return ans;
	}
	vi res1 = solve(L);
	vi res2 = solve(R);
	int mx=0;
	int mx2=0;
	for(int i=0;i<res1.size();i++) mx=max(mx,res1[i]);
	for(int i=0;i<res2.size();i++) mx2=max(mx2,res2[i]);
	mx++; mx2++;
	int intersect = mx+mx2-col;
	if(intersect==0)
	{
		vi ans;
		for(int i=0;i<res1.size();i++) ans.pb(res1[i]);
		for(int i=0;i<res2.size();i++) ans.pb(mx+res2[i]);
		return ans;
	}
	//cerr<<"INTERSECT : "<<intersect<<'\n';
	vi rep1(mx,-1);
	vi rep2(mx2,-1);
	for(int i = 0; i < res1.size(); i++)
	{
		if(rep1[res1[i]]==-1)
		{
			rep1[res1[i]]=i;
		}
	}
	for(int i = 0; i < res2.size(); i++)
	{
		if(rep2[res2[i]]==-1)
		{
			rep2[res2[i]]=i;
		}
	}
	int ptr=intersect;
	int ptr2=mx;
	vi V1,V2,ori1,ori2;
	vi tp;
	for(int i=0;i<mx2;i++) tp.pb(R[rep2[i]]);
	int cur=mx2;
	vi ans(mx+mx2);
	for(int i = 0; i < mx; i++)
	{
		tp.pb(L[rep1[i]]);
		int cur2 = col;
		if(i+1<mx) cur2=query(tp);
		if(cur2>cur)
		{
			ans[i] = ptr++;
		}
		else
		{
			ori1.pb(L[rep1[i]]);
			V1.pb(i);
		}
		cur=cur2;
	}
	tp.clear();
	for(int i=0;i<mx;i++) tp.pb(L[rep1[i]]);
	cur=mx;
	for(int i = 0; i < mx2; i++)
	{
		tp.pb(R[rep2[i]]);
		int cur2 = col;
		if(i+1<mx2) cur2=query(tp);
		if(cur2>cur)
		{
			ans[i+mx] = ptr2++;
		}
		else
		{
			ori2.pb(R[rep2[i]]);
			V2.pb(i+mx);
		}
		cur=cur2;
	}
	pair<vi,vi> tmp = solve2(V1,V2,ori1,ori2);
	for(int i = 0; i < V1.size(); i++)
	{
		ans[V1[i]] = tmp.fi[i];
	}
	for(int i = 0; i < V2.size(); i++)
	{
		ans[V2[i]] = tmp.se[i];
	}
	vi ANS(n);
	/*
	cerr<<"QUESTION : ";
	for(int i=0;i<n;i++) cerr<<vec[i]<<' ';
	cerr<<'\n';
	cerr<<"ANSWER : ";
	*/
	for(int i = 0; i < n; i++)
	{
		if(i<n/2)
		{
			int tmp = res1[i];
			ANS[i] = ans[tmp];
		}
		else
		{
			int tmp = res2[i-n/2];
			ANS[i] = ans[tmp+mx];
		}
		//cerr<<ANS[i]<<' ';
	}
	//cerr<<'\n';
	return ANS;
}

int main()
{
	srand(147);
	int n; cin>>n;
	if(DEBUG)
	{
		for(int i=0;i<n;i++)
		{
			cin>>a[i];
		}
	}
	vi vec;
	for(int i=0;i<n;i++) vec.pb(i);
	vi tmp=solve(vec);
	cout<<0<<' ';
	for(int i=0;i<n;i++)
	{
		cout<<tmp[i]+1;
		if(i+1<n) cout<<' ';
	}
	cout<<'\n';
	fflush(stdout);
}

Compilation message

carnival.cpp: In function 'int query(vi&)':
carnival.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
               ^
carnival.cpp:33:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1<vec.size()) cout<<' ';
         ^
carnival.cpp:42:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<vec.size();i++) s.insert(a[vec[i]]);  
                ^
carnival.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > solve2(vi&, vi&, vi&, vi&)':
carnival.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < orir.size(); i++)
                   ^
carnival.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<Lidx.size();i++)
                ^
carnival.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<Ridx.size();i++)
                ^
carnival.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < Lidx.size(); i++)
                   ^
carnival.cpp:124:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < Ridx.size(); i++)
                   ^
carnival.cpp: In function 'vi solve(vi&)':
carnival.cpp:190:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<res1.size();i++) mx=max(mx,res1[i]);
               ^
carnival.cpp:191:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<res2.size();i++) mx2=max(mx2,res2[i]);
               ^
carnival.cpp:197:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<res1.size();i++) ans.pb(res1[i]);
                ^
carnival.cpp:198:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<res2.size();i++) ans.pb(mx+res2[i]);
                ^
carnival.cpp:204:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < res1.size(); i++)
                   ^
carnival.cpp:211:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < res2.size(); i++)
                   ^
carnival.cpp:261:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < V1.size(); i++)
                   ^
carnival.cpp:265:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < V2.size(); i++)
                   ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2032 KB Output is correct
2 Correct 6 ms 2032 KB Output is correct
3 Correct 9 ms 2032 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 0 ms 2032 KB Output is correct
7 Correct 6 ms 2032 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2032 KB Output is correct
2 Correct 6 ms 2032 KB Output is correct
3 Correct 6 ms 2032 KB Output is correct
4 Correct 3 ms 2032 KB Output is correct
5 Correct 3 ms 2032 KB Output is correct
6 Correct 0 ms 2032 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 0 ms 2032 KB Output is correct
6 Correct 3 ms 2032 KB Output is correct
7 Correct 6 ms 2032 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2032 KB Output is correct
2 Correct 6 ms 2032 KB Output is correct
3 Correct 0 ms 2032 KB Output is correct
4 Correct 0 ms 2032 KB Output is correct
5 Correct 3 ms 2032 KB Output is correct
6 Correct 3 ms 2032 KB Output is correct
7 Correct 0 ms 2032 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2032 KB Output is correct
2 Correct 0 ms 2032 KB Output is correct
3 Correct 3 ms 2032 KB Output is correct
4 Correct 6 ms 2032 KB Output is correct
5 Correct 6 ms 2032 KB Output is correct
6 Correct 3 ms 2032 KB Output is correct
7 Correct 6 ms 2032 KB Output is correct