oj.uz

Submission #116651

# Submission time Handle Problem Language Result Execution time Memory
116651 2019-06-13T10:29:54 Z roseanne_pcy Carnival (CEOI14_carnival) C++14
100 / 100
 10 ms 432 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 155;

vector<int> cand[maxn];

int col[maxn];

int ask(vector<int> vec)
{
	printf("%d ", vec.size());
	for(int x : vec) printf("%d ", x);
	printf("\n");
	fflush(stdout);
	int res; scanf("%d", &res);
	return res;
}

int solve(vector<int> poss, int x)
{
	if(poss.size() == 1)
	{
		return col[poss[0]];
	}
	int lo = 0, hi = (int) poss.size()-1;
	int mid = (lo+hi)/2;
	vector<int> a1, a2;
	for(int i = 0; i<= hi; i++)
	{
		if(i<= mid) a1.pb(poss[i]);
		else a2.pb(poss[i]);
	}
	vector<int> send = a1;
	send.pb(x);
	int res = ask(send);
	if(res == send.size()) return solve(a2, x);
	return solve(a1, x);
}

int main()
{
	int n; scanf("%d", &n);
	col[1] = 1;
	cand[1].pb(1);
	int lim = 1;
	for(int i = 2; i<= n; i++)
	{
		vector<int> send;
		for(int j = 1; j<= lim; j++) send.pb(cand[j].back());
		send.pb(i);
		int res = ask(send);
		if(res == lim+1)
		{
			col[i] = lim+1;
			cand[lim+1].pb(i);
			lim++;
			continue;
		}
		send.pop_back();
		col[i] = solve(send, i);
		cand[col[i]].pb(i);
	}
	printf("0 ");
	for(int i = 1; i<= n; i++) printf("%d ", col[i]);
	printf("\n");
	fflush(stdout);
}

Compilation message

carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:19:26: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d ", vec.size());
                ~~~~~~~~~~^
carnival.cpp: In function 'int solve(std::vector<int>, int)':
carnival.cpp:44:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(res == send.size()) return solve(a2, x);
     ~~~~^~~~~~~~~~~~~~
carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:23:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int res; scanf("%d", &res);
           ~~~~~^~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d", &n);
         ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 256 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 7 ms 256 KB Output is correct
4 Correct 3 ms 432 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 8 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 408 KB Output is correct
3 Correct 6 ms 416 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 408 KB Output is correct
6 Correct 6 ms 256 KB Output is correct
7 Correct 7 ms 256 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 10 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 7 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 8 ms 256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 256 KB Output is correct
2 Correct 9 ms 256 KB Output is correct
3 Correct 7 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Correct 7 ms 256 KB Output is correct
7 Correct 5 ms 324 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 9 ms 256 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 9 ms 256 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 3 ms 328 KB Output is correct