oj.uz

Submission #440445

# Submission time Handle Problem Language Result Execution time Memory
440445 2021-07-02T09:24:37 Z dutch ICC (CEOI16_icc) C++17
100 / 100
 133 ms 580 KB 
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
 
vector<int> g[100];
 
bool ask(vector<int> x[2]){
	int a[2][100], p[2] = {0, 0}, k = -1;
	while(++k<2) for(int i : x[k]) for(int j : g[i]) a[k][p[k]++] = j;
	return p[0] && p[1] && query(p[0], p[1], a[0], a[1]);
}
 
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, l, r;
		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)) 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));
		}
		y = a[y], x ^= y;
		setRoad(g[y][bs(y, x)], g[x][bs(x, y)]);
 
		for(int i : g[y]) g[x].push_back(i);
		g[y].swap(g[c-1]);
	}
}

Compilation message

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

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 39 ms 476 KB Ok! 618 queries used.
2 Correct 30 ms 460 KB Ok! 444 queries used.
3 Correct 33 ms 460 KB Ok! 512 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 484 KB Ok! 1558 queries used.
2 Correct 105 ms 460 KB Ok! 1097 queries used.
3 Correct 132 ms 460 KB Ok! 1552 queries used.
4 Correct 126 ms 460 KB Ok! 1539 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 460 KB Ok! 1528 queries used.
2 Correct 124 ms 500 KB Ok! 1531 queries used.
3 Correct 123 ms 500 KB Ok! 1524 queries used.
4 Correct 133 ms 480 KB Ok! 1551 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 492 KB Ok! 1500 queries used.
2 Correct 122 ms 580 KB Ok! 1520 queries used.
3 Correct 124 ms 492 KB Ok! 1439 queries used.
4 Correct 126 ms 496 KB Ok! 1544 queries used.
5 Correct 126 ms 496 KB Ok! 1539 queries used.
6 Correct 123 ms 460 KB Ok! 1492 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 500 KB Ok! 1512 queries used.
2 Correct 113 ms 460 KB Ok! 1253 queries used.