oj.uz

Submission #67321

# Submission time Handle Problem Language Result Execution time Memory
67321 2018-08-14T00:58:35 Z Mamnoon_Siam Carnival (CEOI14_carnival) C++17
100 / 100
 37 ms 572 KB 
// #define local

#include <bits/stdc++.h>
using namespace std;

int n;

#ifdef local
int wot[1 << 8];
int ask_local(vector<int> &vec) {
	set<int> st;
	for(int b : vec) {
		st.insert(wot[b]);
	} return st.size();
}
#endif

int ask(vector<int> &vec) {
	#ifdef local
	return ask_local(vec);
	#endif
	#ifndef local
	cout << vec.size() << ' ';
	for(int b : vec) cout << b + 1 << ' '; cout << endl;
	int ret; cin >> ret;
	return ret;
	#endif
}
int askn() {
	#ifdef local
	return n;
	#endif
	#ifndef local
	int ret; cin >> ret; return ret;
	#endif
}
void printsoln(vector<int> &ans) {
	cout << "0 ";
	for(int b : ans) cout << b + 1 << ' '; cout << endl;
}

int32_t main() {
	#ifdef local
	freopen("in", "r", stdin);
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> wot[i];
	#endif
	
	n = askn();
	vector<vector<int>> g(n);
	for(int i = 0; i < g.size(); i++)
		g[i].emplace_back(i);

	while(true) {
		{
			vector<int> ls;
			for(int i = 0; i < g.size(); i++) {
				ls.insert(ls.end(), g[i].begin(), g[i].end());
			}
			if(ask(ls) == g.size()) {
				break;
			}
		}
		int L = -1, R = -1, lo, hi, mid;

		lo = 0, hi = g.size() - 1;
		while(lo <= hi) {
			mid = lo + hi >> 1;
			vector<int> ls;
			for(int i = 0; i <= mid; i++) {
				ls.insert(ls.end(), g[i].begin(), g[i].end());
			}
			if(ask(ls) < mid + 1) {
				R = mid;
				hi = mid - 1;
			}  else {
				lo = mid + 1;
			}
		}

		lo = 0, hi = R;
		while(lo <= hi) {
			mid = lo + hi >> 1;
			vector<int> ls;
			for(int i = mid; i <= R; i++) {
				ls.insert(ls.end(), g[i].begin(), g[i].end());
			}
			if(ask(ls) < R - mid + 1) {
				L = mid;
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}

		g[L].insert(g[L].end(), g[R].begin(), g[R].end());
		g.erase(g.begin() + R);
	}
	vector<int> ans(n);
	for(int i = 0; i < g.size(); i++) {
		for(int b : g[i]) {
			ans[b] = i;
		}
	}
	printsoln(ans);
}

Compilation message

carnival.cpp: In function 'int ask(std::vector<int>&)':
carnival.cpp:24:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int b : vec) cout << b + 1 << ' '; cout << endl;
  ^~~
carnival.cpp:24:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int b : vec) cout << b + 1 << ' '; cout << endl;
                                         ^~~~
carnival.cpp: In function 'void printsoln(std::vector<int>&)':
carnival.cpp:39:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int b : ans) cout << b + 1 << ' '; cout << endl;
  ^~~
carnival.cpp:39:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int b : ans) cout << b + 1 << ' '; cout << endl;
                                         ^~~~
carnival.cpp: In function 'int32_t main()':
carnival.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g.size(); i++)
                 ~~^~~~~~~~~~
carnival.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < g.size(); i++) {
                   ~~^~~~~~~~~~
carnival.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ask(ls) == g.size()) {
       ~~~~~~~~^~~~~~~~~~~
carnival.cpp:69:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = lo + hi >> 1;
          ~~~^~~~
carnival.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = lo + hi >> 1;
          ~~~^~~~
carnival.cpp:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g.size(); i++) {
                 ~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 308 KB Output is correct
2 Correct 23 ms 436 KB Output is correct
3 Correct 10 ms 436 KB Output is correct
4 Correct 6 ms 540 KB Output is correct
5 Correct 25 ms 540 KB Output is correct
6 Correct 28 ms 540 KB Output is correct
7 Correct 19 ms 540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 540 KB Output is correct
2 Correct 31 ms 540 KB Output is correct
3 Correct 11 ms 540 KB Output is correct
4 Correct 8 ms 568 KB Output is correct
5 Correct 26 ms 568 KB Output is correct
6 Correct 37 ms 568 KB Output is correct
7 Correct 21 ms 568 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 568 KB Output is correct
2 Correct 32 ms 568 KB Output is correct
3 Correct 28 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 22 ms 568 KB Output is correct
6 Correct 23 ms 568 KB Output is correct
7 Correct 22 ms 568 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 568 KB Output is correct
2 Correct 28 ms 568 KB Output is correct
3 Correct 10 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 25 ms 568 KB Output is correct
6 Correct 18 ms 568 KB Output is correct
7 Correct 25 ms 568 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 568 KB Output is correct
2 Correct 26 ms 568 KB Output is correct
3 Correct 23 ms 568 KB Output is correct
4 Correct 14 ms 568 KB Output is correct
5 Correct 22 ms 572 KB Output is correct
6 Correct 9 ms 572 KB Output is correct
7 Correct 5 ms 572 KB Output is correct