oj.uz

Submission #104382

# Submission time Handle Problem Language Result Execution time Memory
104382 2019-04-06T06:40:22 Z hugo_pm Carnival (CEOI14_carnival) C++17
100 / 100
 42 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= b; --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void cpr(string s, vector<int> v)
{ int i = 0; for (char c : s) { if (c == '$') cout << v[i++]; else cout << c; } cout << '\n'; }

void cpr(string s) { cpr(s, {}); }

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne = 155;
int coul[borne];
int jusq[borne];
vector<int> adj[borne];
int nbPart;
int nbCoul=0;

int ask(vector<int> v)
{
	int sz = v.size();
	if (sz == 0) return 0;
	cout << sz;
	form(i, sz) cout << " " << v[i]+1;
	cout << "\n" << flush;
	int rr2; cin >> rr2;
	return rr2;
}

int ask2(int l, int r)
{
	vector<int> v;
	form2(i, l, r+1) v.push_back(i);
	return ask(v);
}

void build(int x)
{
	int l = x, r = nbPart-1;
	while (l < r) {
		int m = (l+r+1) / 2;
		if (ask2(x,m) == ask2(x+1,m)+1) l = m;
		else r = m-1;
	}
	if (r != nbPart-1) {
		adj[x].push_back(r+1);
		adj[r+1].push_back(x);
	}
}

void dfs(int x, int c)
{
	coul[x] = c;
	for (int vo : adj[x]) if (coul[vo] == 0) {
		dfs(vo, c);
	}
}

void solve()
{
	cin >> nbPart;
	form(i, nbPart) build(i);
	form(i, nbPart) if (coul[i] == 0) dfs(i, ++nbCoul);
	cout << "0";
	form(i, nbPart) cout << " " << coul[i];
	cout << "\n" << flush;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 256 KB Output is correct
2 Correct 19 ms 256 KB Output is correct
3 Correct 18 ms 384 KB Output is correct
4 Correct 24 ms 384 KB Output is correct
5 Correct 8 ms 256 KB Output is correct
6 Correct 19 ms 256 KB Output is correct
7 Correct 17 ms 256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 256 KB Output is correct
2 Correct 25 ms 304 KB Output is correct
3 Correct 21 ms 256 KB Output is correct
4 Correct 42 ms 256 KB Output is correct
5 Correct 24 ms 384 KB Output is correct
6 Correct 18 ms 384 KB Output is correct
7 Correct 20 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 256 KB Output is correct
2 Correct 17 ms 256 KB Output is correct
3 Correct 32 ms 384 KB Output is correct
4 Correct 39 ms 384 KB Output is correct
5 Correct 21 ms 256 KB Output is correct
6 Correct 15 ms 256 KB Output is correct
7 Correct 27 ms 384 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 384 KB Output is correct
2 Correct 18 ms 384 KB Output is correct
3 Correct 27 ms 256 KB Output is correct
4 Correct 30 ms 256 KB Output is correct
5 Correct 22 ms 384 KB Output is correct
6 Correct 27 ms 256 KB Output is correct
7 Correct 13 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 304 KB Output is correct
2 Correct 25 ms 384 KB Output is correct
3 Correct 36 ms 256 KB Output is correct
4 Correct 32 ms 256 KB Output is correct
5 Correct 25 ms 384 KB Output is correct
6 Correct 19 ms 256 KB Output is correct
7 Correct 19 ms 384 KB Output is correct