Submission #340703

# Submission time Handle Problem Language Result Execution time Memory
340703 2020-12-28T08:28:41 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];
bool ask(vector<int>v){
	printf("%d ",int(v.size()));
	tr(it,v)printf("%d ",*it);cout<<endl;
	int res;scanf("%d",&res);return (res==int(v.size()));
}
int main(){
    int n;scanf("%d",&n);
    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);
	    }
	    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);
	    }
    }
    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;
    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:24:2: note: in expansion of macro 'tr'
   24 |  tr(it,v)printf("%d ",*it);cout<<endl;
      |  ^~
carnival.cpp:24:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   24 |  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:34:6: note: in expansion of macro 'tr'
   34 |      tr(it,v)found|=(*it==i);if(found)continue;
      |      ^~
carnival.cpp:34:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   34 |      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:37:6: note: in expansion of macro 'tr'
   37 |      tr(it,v)if(*it<i)a.pb(*it);a.pb(i);
      |      ^~
carnival.cpp:37:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   37 |      tr(it,v)if(*it<i)a.pb(*it);a.pb(i);
      |                                 ^
carnival.cpp:47:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   47 |    if(ask(c))st--;adj[a[st]].pb(i);
      |    ^~
carnival.cpp:47:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   47 |    if(ask(c))st--;adj[a[st]].pb(i);
      |                   ^~~
carnival.cpp:58:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   58 |    if(ask(c))en++;adj[b[en]].pb(i);
      |    ^~
carnival.cpp:58:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   58 |    if(ask(c))en++;adj[b[en]].pb(i);
      |                   ^~~
carnival.cpp:64:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   64 |     for(int i=1;i<=n;i++)printf("%d ",arr[i]);cout<<endl;
      |     ^~~
carnival.cpp:64:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   64 |     for(int i=1;i<=n;i++)printf("%d ",arr[i]);cout<<endl;
      |                                               ^~~~
carnival.cpp: In function 'bool ask(std::vector<int>)':
carnival.cpp:25:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  int res;scanf("%d",&res);return (res==int(v.size()));
      |          ~~~~~^~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:28:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |     int n;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 9 ms 2668 KB Output is correct
4 Correct 5 ms 2668 KB Output is correct
5 Correct 6 ms 2668 KB Output is correct
6 Correct 6 ms 2668 KB Output is correct
7 Correct 11 ms 2668 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 6 ms 2736 KB Output is correct
2 Correct 12 ms 2668 KB Output is correct
3 Correct 7 ms 2668 KB Output is correct
4 Correct 6 ms 2668 KB Output is correct
5 Correct 9 ms 2668 KB Output is correct
6 Correct 7 ms 2796 KB Output is correct
7 Correct 10 ms 2668 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 5 ms 2668 KB Output is correct
2 Correct 9 ms 2668 KB Output is correct
3 Correct 13 ms 2740 KB Output is correct
4 Correct 5 ms 2700 KB Output is correct
5 Correct 9 ms 2668 KB Output is correct
6 Correct 10 ms 2668 KB Output is correct
7 Correct 14 ms 2668 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 8 ms 2668 KB Output is correct
2 Correct 11 ms 2736 KB Output is correct
3 Correct 8 ms 2668 KB Output is correct
4 Correct 6 ms 2668 KB Output is correct
5 Correct 13 ms 2668 KB Output is correct
6 Correct 14 ms 2744 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 11 ms 2668 KB Output is correct
3 Correct 12 ms 2668 KB Output is correct
4 Correct 9 ms 2668 KB Output is correct
5 Correct 11 ms 2796 KB Output is correct
6 Correct 10 ms 2796 KB Output is correct
7 Correct 7 ms 2668 KB Output is correct