Submission #340702

# Submission time Handle Problem Language Result Execution time Memory
340702 2020-12-28T08:27:55 Z Kerim Carnival (CEOI14_carnival) C++17
100 / 100
14 ms 2796 KB
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int arr[MAXN],ans[MAXN];
vector<int>adj[MAXN];
set<int>s;
bool ask(vector<int>v){
	printf("%d ",int(v.size()));
	tr(it,v)printf("%d ",*it);cout<<endl;
	//s.clear();tr(it,v)s.insert(ans[*it]);return (int(s.size())==int(v.size()));
	int res;scanf("%d",&res);return (res==int(v.size()));
}
int main(){
	//freopen("file.in","r",stdin);
    int n;
    scanf("%d",&n);
    //for(int i=1;i<=n;i++)
    //	scanf("%d",ans+i);
    vector<int>v;v.pb(1);
    for(int i=2;i<=n;i++){v.pb(i);
		if(!ask(v))v.ppb();
    }tr(it,v)adj[*it].pb(*it);
    for(int i=1;i<=n;i++){int found=0;
    	tr(it,v)found|=(*it==i);if(found)continue;
    	vector<int>a,b,c;b.pb(i);
    	tr(it,v)if(*it>i)b.pb(*it);
    	tr(it,v)if(*it<i)a.pb(*it);a.pb(i);
    	if(!ask(a)){
	    	int st=1,en=int(a.size())-1;
	    	while(st+1<en){
	    		int mid=(st+en)>>1;c.clear();
	    		for(int j=mid;j<int(a.size());j++)c.pb(a[j]);	
				if(ask(c))en=mid;
				else st=mid;
			}c.clear();
    		for(int j=st;j<int(a.size());j++)c.pb(a[j]);	
			if(ask(c))st--;
			adj[a[st]].pb(i);
			//printf("%d %d\n",i,a[st]);
	    }
	    else{
	    	int st=0,en=int(a.size())-2;
	    	while(st+1<en){
	    		int mid=(st+en)>>1;c.clear();
	    		for(int j=mid;j<int(b.size());j++)c.pb(b[j]);	
				if(ask(c))st=mid;
				else en=mid;
			}c.clear();
    		for(int j=en;j<int(b.size());j++)c.pb(a[j]);	
			if(ask(c))en++;
			adj[b[en]].pb(i);
			//printf("%d %d\n",i,b[en]);
	    }
    }
    for(int i=0;i<int(v.size());i++)
    	tr(it,adj[v[i]])arr[*it]=i+1;
    printf("0 ");
    for(int i=1;i<=n;i++)printf("%d ",arr[i]);cout<<endl;
    exit(0);
    for(int i=1;i<n;i++)
    	for(int j=i+1;j<=n;j++)
    		assert((ans[i]==ans[j])==(arr[i]==arr[j]));
	return 0;
}

Compilation message

carnival.cpp: In function 'bool ask(std::vector<int>)':
carnival.cpp:9:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
      |                  ^~~
carnival.cpp:25:2: note: in expansion of macro 'tr'
   25 |  tr(it,v)printf("%d ",*it);cout<<endl;
      |  ^~
carnival.cpp:25:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   25 |  tr(it,v)printf("%d ",*it);cout<<endl;
      |                            ^~~~
carnival.cpp: In function 'int main()':
carnival.cpp:9:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
      |                  ^~~
carnival.cpp:40:6: note: in expansion of macro 'tr'
   40 |      tr(it,v)found|=(*it==i);if(found)continue;
      |      ^~
carnival.cpp:40:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |      tr(it,v)found|=(*it==i);if(found)continue;
      |                              ^~
carnival.cpp:9:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
      |                  ^~~
carnival.cpp:43:6: note: in expansion of macro 'tr'
   43 |      tr(it,v)if(*it<i)a.pb(*it);a.pb(i);
      |      ^~
carnival.cpp:43:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   43 |      tr(it,v)if(*it<i)a.pb(*it);a.pb(i);
      |                                 ^
carnival.cpp:74:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   74 |     for(int i=1;i<=n;i++)printf("%d ",arr[i]);cout<<endl;
      |     ^~~
carnival.cpp:74:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   74 |     for(int i=1;i<=n;i++)printf("%d ",arr[i]);cout<<endl;
      |                                               ^~~~
carnival.cpp:76:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   76 |     for(int i=1;i<n;i++)
      |     ^~~
carnival.cpp:79:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   79 |  return 0;
      |  ^~~~~~
carnival.cpp: In function 'bool ask(std::vector<int>)':
carnival.cpp:27:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  int res;scanf("%d",&res);return (res==int(v.size()));
      |          ~~~~~^~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 10 ms 2668 KB Output is correct
2 Correct 13 ms 2668 KB Output is correct
3 Correct 8 ms 2668 KB Output is correct
4 Correct 5 ms 2668 KB Output is correct
5 Correct 7 ms 2668 KB Output is correct
6 Correct 6 ms 2668 KB Output is correct
7 Correct 13 ms 2796 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 2668 KB Output is correct
2 Correct 12 ms 2668 KB Output is correct
3 Correct 7 ms 2736 KB Output is correct
4 Correct 6 ms 2668 KB Output is correct
5 Correct 10 ms 2668 KB Output is correct
6 Correct 10 ms 2668 KB Output is correct
7 Correct 11 ms 2796 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 2736 KB Output is correct
2 Correct 10 ms 2668 KB Output is correct
3 Correct 12 ms 2668 KB Output is correct
4 Correct 5 ms 2668 KB Output is correct
5 Correct 9 ms 2668 KB Output is correct
6 Correct 10 ms 2668 KB Output is correct
7 Correct 12 ms 2668 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 7 ms 2668 KB Output is correct
2 Correct 10 ms 2668 KB Output is correct
3 Correct 10 ms 2668 KB Output is correct
4 Correct 6 ms 2796 KB Output is correct
5 Correct 14 ms 2668 KB Output is correct
6 Correct 10 ms 2668 KB Output is correct
7 Correct 12 ms 2668 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 2668 KB Output is correct
2 Correct 14 ms 2668 KB Output is correct
3 Correct 8 ms 2736 KB Output is correct
4 Correct 10 ms 2668 KB Output is correct
5 Correct 11 ms 2668 KB Output is correct
6 Correct 8 ms 2668 KB Output is correct
7 Correct 5 ms 2736 KB Output is correct