oj.uz

Submission #152760

# Submission time Handle Problem Language Result Execution time Memory
152760 2019-09-09T11:56:44 Z junodeveloper Carnival (CEOI14_carnival) C++14
100 / 100
 29 ms 424 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, par[151];
int T[1010];
int pn(int u){return u==par[u]?u:(par[u]=pn(par[u]));}
void us(int a,int b) {
	a=pn(a),b=pn(b);
	par[b]=a;
}
int query(int p,int l,int r) {
	printf("%d ",r-l+2);
	int i;
	printf("%d ",p);
	for(i=l;i<=r;i++) printf("%d ",i);
	fflush(stdout);
	int ret;
	scanf("%d",&ret);
	return ret;
}
void solve(int h,int l,int r) {
	if(l==r) {
		T[h]=1;
		return;
	}
	int mid=(l+r)/2;
	solve(h*2,l,mid);
	solve(h*2+1,mid+1,r);
	int i,ret;
	for(i=l;i<=mid;i++) {
		ret=query(i,mid+1,r);
		if(ret==T[h*2+1]+1) continue;
		else {
			int cur=h*2+1, tl=mid+1, tr=r;
			while(tl<tr) {
				int tmid=(tl+tr)/2;
				int tret=query(i,tl,tmid);
				if(tret==T[cur*2]+1) {
					tl=tmid+1;
					cur=cur*2+1;
				} else {
					tr=tmid;
					cur=cur*2;
				}
			}
			us(i,tl);
		}
	}
	vector<int> v;
	for(i=l;i<=r;i++)v.push_back(pn(i));
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	T[h]=sz(v);
}
int main() {
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++) par[i]=i;
	solve(1,1,n);
	vector<int> v;
	for(i=1;i<=n;i++) {
		v.push_back(pn(i));
	}
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	printf("0 ");
	for(i=1;i<=n;i++) {
		int p=pn(i);
		p=lower_bound(all(v),p)-v.begin()+1;
		printf("%d ",p);
	}
	fflush(stdout);
	return 0;
}

Compilation message

carnival.cpp: In function 'int query(int, int, int)':
carnival.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&ret);
  ~~~~~^~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 376 KB Output is correct
2 Correct 15 ms 376 KB Output is correct
3 Correct 10 ms 320 KB Output is correct
4 Correct 9 ms 248 KB Output is correct
5 Correct 29 ms 248 KB Output is correct
6 Correct 29 ms 376 KB Output is correct
7 Correct 18 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 424 KB Output is correct
2 Correct 20 ms 248 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 10 ms 248 KB Output is correct
5 Correct 28 ms 376 KB Output is correct
6 Correct 29 ms 248 KB Output is correct
7 Correct 28 ms 316 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 316 KB Output is correct
2 Correct 13 ms 376 KB Output is correct
3 Correct 8 ms 320 KB Output is correct
4 Correct 9 ms 380 KB Output is correct
5 Correct 26 ms 248 KB Output is correct
6 Correct 26 ms 376 KB Output is correct
7 Correct 20 ms 424 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 324 KB Output is correct
2 Correct 28 ms 320 KB Output is correct
3 Correct 7 ms 316 KB Output is correct
4 Correct 9 ms 376 KB Output is correct
5 Correct 23 ms 320 KB Output is correct
6 Correct 21 ms 376 KB Output is correct
7 Correct 11 ms 316 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 320 KB Output is correct
2 Correct 13 ms 320 KB Output is correct
3 Correct 14 ms 248 KB Output is correct
4 Correct 11 ms 320 KB Output is correct
5 Correct 20 ms 376 KB Output is correct
6 Correct 16 ms 248 KB Output is correct
7 Correct 10 ms 248 KB Output is correct