oj.uz

Submission #440430

# Submission time Handle Problem Language Result Execution time Memory
440430 2021-07-02T09:10:14 Z dutch ICC (CEOI16_icc) C++17
100 / 100
 157 ms 500 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;

vector<int> g[100];

bool ask(vector<int> &x, vector<int> &y){
	int a[100], b[100], pA = 0, pB = 0;
	for(int i : x) for(int j : g[i]) a[pA++] = j;
	for(int i : y) for(int j : g[i]) b[pB++] = j;
	return pA && pB && query(pA, pB, a, b);
}

int bs(int x, int y){
	int r = 0;
	int gy[g[y].size()];
	for(int i=0; i<g[y].size(); ++i) gy[i] = g[y][i];
	for(int s=128; s/=2; ){
		if(r + s >= g[x].size()) continue;
		int q[r+s];
		for(int i=0; i<r+s; ++i) q[i] = g[x][i];
		r += s * (!query(r+s, g[y].size(), q, gy));
	}
	return r;
}

void run(int n){
	for(int i=0; i<n; ++i) g[i].push_back(i+1);
	for(int c=n; c>1; --c){
		int x = 0, y = 0;
		for(int i=1; i<=c; i+=i){
			vector<int> q[2];
			for(int j=0; j<c; ++j) q[bool(j & i)].push_back(j);
			if(ask(q[0], q[1])) x |= i;
		}
		vector<int> a;
		for(int i=0; i<c; ++i) if(i<(i^x) && (i^x)<c) a.push_back(i);

		for(int s=128; s/=2; ){
			if(y + s >= a.size()) continue;
			vector<int> q[2];
			for(int i=0; i<y+s; ++i){
				q[0].push_back(a[i]);
				q[1].push_back(a[i] ^ x);
			}
			y += s * (!ask(q[0], q[1]));
		}
		y = a[y];
		int l = bs(y, x ^ y);
		int r = bs(x ^ y, y);
		setRoad(g[y][l], g[x ^ y][r]);

		for(int i : g[y]) g[x^y].push_back(i);
		vector<int> ().swap(g[y]);

		for(int i=0; i+1<c; ++i) if(g[i].empty()) swap(g[i], g[c-1]);
	}
}

Compilation message

icc.cpp: In function 'int bs(int, int)':
icc.cpp:17:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0; i<g[y].size(); ++i) gy[i] = g[y][i];
      |               ~^~~~~~~~~~~~
icc.cpp:19:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   if(r + s >= g[x].size()) continue;
      |      ~~~~~~^~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:40:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    if(y + s >= a.size()) continue;
      |       ~~~~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 460 KB Ok! 111 queries used.
2 Correct 7 ms 460 KB Ok! 108 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 460 KB Ok! 618 queries used.
2 Correct 33 ms 488 KB Ok! 462 queries used.
3 Correct 35 ms 460 KB Ok! 512 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 500 KB Ok! 1558 queries used.
2 Correct 104 ms 500 KB Ok! 1094 queries used.
3 Correct 130 ms 492 KB Ok! 1552 queries used.
4 Correct 125 ms 460 KB Ok! 1539 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 480 KB Ok! 1526 queries used.
2 Correct 157 ms 476 KB Ok! 1531 queries used.
3 Correct 137 ms 496 KB Ok! 1524 queries used.
4 Correct 129 ms 496 KB Ok! 1551 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 492 KB Ok! 1500 queries used.
2 Correct 136 ms 460 KB Ok! 1520 queries used.
3 Correct 145 ms 496 KB Ok! 1436 queries used.
4 Correct 154 ms 488 KB Ok! 1544 queries used.
5 Correct 140 ms 496 KB Ok! 1539 queries used.
6 Correct 140 ms 480 KB Ok! 1492 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 496 KB Ok! 1512 queries used.
2 Correct 114 ms 480 KB Ok! 1253 queries used.