제출 #440430

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440430		dutch	ICC (CEOI16_icc)	C++17	100 / 100	157 ms	500 KiB

icc

#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]);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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