oj.uz

Submission #46877

# Submission time Handle Problem Language Result Execution time Memory
46877 2018-04-24T13:01:11 Z bugmenot111 Carnival (CEOI14_carnival) C++17
100 / 100
 19 ms 616 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
typedef std::vector<int> vector;
int query(vector v) { // this is why C++ > Haskell
	int ans;
	if(v.size() == 0) return 0;
	printf("%lu", v.size());
	for(int c: v) printf(" %d", c);
	putchar('\n');
	fflush(stdout);
	scanf("%d", &ans);
	return ans;
}
void yes(vector v) {
	putchar('0');
	for(int c: v) printf(" %d", c);
	putchar('\n');
	fflush(stdout);
}
vector solve(int l, int r) {
	int m, l1, r1, m1, i, j, mx1, mx2, c, cur;
	int rep1[210] = {0};
	int rep2[210] = {0};
	int now[210] = {0};
	vector v1, v2, qr;
	if(l == r) return {1};
	m = (l + r) / 2;
	v1 = solve(l, m);
	v2 = solve(m + 1, r);
	for(i = 0; i < v1.size(); i++) rep1[v1[i]] = l + i;
	for(i = 0; i < v2.size(); i++) rep2[v2[i]] = m + 1 + i;
	mx1 = *std::max_element(v1.begin(), v1.end());
	mx2 = *std::max_element(v2.begin(), v2.end());
	cur = mx2;
	for(i = 1; i <= mx1; i++) {
		c = rep1[i];
		l1 = 1;
		r1 = mx2 + 1;
		while(l1 < r1) {
			m1 = (l1 + r1) / 2;
			for(j = 1; j <= m1; j++) qr.push_back(rep2[j]);
			qr.push_back(c);
			if(m1 == mx2 + 1 || query(qr) == m1) r1 = m1;
			else l1 = m1 + 1;
			qr.clear();
		}
		now[i] = l1 == mx2 + 1 ? ++cur : l1;
	}
	for(i = 0; i < v1.size(); i++)
		v1[i] = now[v1[i]];
	v1.insert(v1.end(), v2.begin(), v2.end());
	return v1;
}
int main(void) {
	int n;
	scanf("%d", &n);
	yes(solve(1, n));
	return 0;
}

Compilation message

carnival.cpp: In function 'vector solve(int, int)':
carnival.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < v1.size(); i++) rep1[v1[i]] = l + i;
             ~~^~~~~~~~~~~
carnival.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < v2.size(); i++) rep2[v2[i]] = m + 1 + i;
             ~~^~~~~~~~~~~
carnival.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i = 0; i < v1.size(); i++)
             ~~^~~~~~~~~~~
carnival.cpp: In function 'int query(vector)':
carnival.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &ans);
  ~~~~~^~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:57: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 6 ms 252 KB Output is correct
2 Correct 9 ms 308 KB Output is correct
3 Correct 14 ms 472 KB Output is correct
4 Correct 15 ms 472 KB Output is correct
5 Correct 3 ms 488 KB Output is correct
6 Correct 3 ms 488 KB Output is correct
7 Correct 8 ms 536 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 536 KB Output is correct
2 Correct 9 ms 536 KB Output is correct
3 Correct 10 ms 540 KB Output is correct
4 Correct 16 ms 572 KB Output is correct
5 Correct 4 ms 572 KB Output is correct
6 Correct 4 ms 572 KB Output is correct
7 Correct 6 ms 572 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 5 ms 588 KB Output is correct
3 Correct 14 ms 588 KB Output is correct
4 Correct 19 ms 588 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 6 ms 588 KB Output is correct
7 Correct 7 ms 616 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 616 KB Output is correct
2 Correct 4 ms 616 KB Output is correct
3 Correct 16 ms 616 KB Output is correct
4 Correct 17 ms 616 KB Output is correct
5 Correct 6 ms 616 KB Output is correct
6 Correct 8 ms 616 KB Output is correct
7 Correct 10 ms 616 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 616 KB Output is correct
2 Correct 9 ms 616 KB Output is correct
3 Correct 18 ms 616 KB Output is correct
4 Correct 14 ms 616 KB Output is correct
5 Correct 9 ms 616 KB Output is correct
6 Correct 17 ms 616 KB Output is correct
7 Correct 17 ms 616 KB Output is correct