oj.uz

Submission #25935

# Submission time Handle Problem Language Result Execution time Memory
25935 2017-06-25T07:12:34 Z 윤교준(#1090) Carnival (CEOI14_carnival) C++11
100 / 100
 9 ms 2028 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (155)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
int ask(const vector<int>& V) {
	printf("%d", sz(V));
	for(int v : V) printf(" %d", v);
	puts("");
	fflush(stdout);
	int ret = 0; scanf("%d", &ret);
	return ret;
}
int ask(int S, int E) {
	if(S == E) { return 1; }
	vector<int> V; for(int i = S; i <= E; i++) V.pb(i);
	return ask(V);
}

int N;

int g(const vector<int>& V, const int T, int S, int E) {
	if(S > E) return -1;
	if(S == E) return S;
	const int M = (S+E)/2;
	vector<int> AV; AV.pb(T);
	for(int i = S; i <= M; i++) AV.pb(V[i]);
	const int ret = ask(AV); clv(AV);
	if((M-S+1) == ret) return g(V, T, S, M);
	return g(V, T, M+1, E);
}
int g(const vector<int>& V, const int T) {
	vector<int> AV; AV = V; AV.pb(T);
	const int ret = ask(AV); clv(AV);
	if(sz(V) == ret) return g(V, T, 0, sz(V)-1);
	return -1;
}
void f(vector<vector<int>>& V, int S, int E, int A) {
	if(S == E) {
		V.resize(1, vector<int>());
		V[0].pb(S);
		return;
	}
	if(S+1 == E) {
		if(1 == A) {
			V.resize(1, vector<int>());
			V[0].pb(S); V[0].pb(E);
		} else {
			V.resize(2, vector<int>());
			V[0].pb(S); V[1].pb(E);
		}
		return;
	}
	const int M = (S+E)/2;
	const int B = ask(S, M), C = ask(M+1, E);
	vector<vector<int>> LV, RV;
	f(LV, S, M, B); f(RV, M+1, E, C);
	const int R = B+C-A;
	vector<int> SV(B, -1);
	vector<int> HV(C);
	for(int i = 0; i < C; i++) HV[i] = RV[i][0];
	for(int i = 0, cnt = 0; i < B && cnt < R; i++) {
		const int ret = g(HV, LV[i][0]);
		if(-1 == ret) continue;
		SV[i] = ret; cnt++;
	}
	clv(HV);
	V.resize(A, vector<int>());
	int idx = 0;
	for(int i = 0; i < B; i++) {
		if(-1 == SV[i]) { V[idx] = LV[i]; idx++; continue; }
		V[idx] = LV[i]; for(int v : RV[SV[i]]) V[idx].pb(v);
		idx++; clv(RV[SV[i]]);
	}
	for(int i = 0; i < C; i++) {
		if(RV[i].empty()) continue;
		V[idx] = RV[i]; idx++;
	}
}

vector<vector<int>> AnsV;
int Ans[MAXN];

int main() {
	scanf("%d", &N);
	f(AnsV, 1, N, ask(1, N));
	for(int i = 0; i < sz(AnsV); i++) {
		for(int v : AnsV[i]) Ans[v] = i+1;
	}
	printf("0");
	for(int i = 1; i <= N; i++) printf(" %d", Ans[i]);
	puts("");
	fflush(stdout);
	return 0;
}

Compilation message

carnival.cpp: In function 'int ask(const std::vector<int>&)':
carnival.cpp:43:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int ret = 0; scanf("%d", &ret);
                                ^
carnival.cpp: In function 'int main()':
carnival.cpp:117:17: 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 3 ms 2028 KB Output is correct
2 Correct 3 ms 2028 KB Output is correct
3 Correct 3 ms 2028 KB Output is correct
4 Correct 3 ms 2028 KB Output is correct
5 Correct 3 ms 2028 KB Output is correct
6 Correct 3 ms 2028 KB Output is correct
7 Correct 6 ms 2028 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

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

Subtask #5
20.0 / 20.0

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