Submission #440445

#	Time	Username	Problem	Language	Result	Execution time	Memory
440445		dutch	ICC (CEOI16_icc)	C++17	100 / 100	133 ms	580 KiB

icc

#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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10