#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
//#define int long long
vector<int> color(105);
vector<vector<int> > comp(105);
int q(vector<int> &a,vector<int> &b){
if(a.size()==0||b.size()==0){
return 0;
}
int aa[(int)a.size()];
int bb[(int)b.size()];
for(int i=0;i<(int)a.size();i++){
aa[i] = a[i];
}
for(int i=0;i<(int)b.size();i++){
bb[i] = b[i];
}
return query(a.size(),b.size(),aa,bb);
}
int qcomp(vector<int> &a,vector<int> &b){
vector<int> temp1,temp2;
for(auto k:a){
for(auto j:comp[k]){
temp1.push_back(j);
}
}
for(auto k:b){
for(auto j:comp[k]){
temp2.push_back(j);
}
}
return q(temp1,temp2);
}
void road(int a,int b){
setRoad(min(a,b),max(a,b));
}
void merge(int a,int b){
for(auto k:comp[color[b]]){
comp[color[a]].push_back(k);
}
int change = color[b];
for(int i=1;i<color.size();i++){
if(color[i]==change){
color[i] = color[a];
}
}
comp[change].clear();
}
void binarysearch(vector<int> left,vector<int> right){
vector<int> temp1;
vector<int> temp2;
for(auto k:left){
for(auto j:comp[k]){
temp1.push_back(j);
}
}
for(auto k:right){
for(auto j:comp[k]){
temp2.push_back(j);
}
}
left = temp1;
right = temp2;
while(left.size()!=1){
vector<int> curr;
for(int i=0;i<(left.size()+1)/2;i++){
curr.push_back(left[i]);
}
vector<int> curr2;
for(int i=(left.size()+1)/2;i<left.size();i++){
curr2.push_back(left[i]);
}
if(q(curr,right)==1){
left = curr;
}
else{
left = curr2;
}
}
swap(left,right);
while(left.size()!=1){
vector<int> curr;
for(int i=0;i<(left.size()+1)/2;i++){
curr.push_back(left[i]);
}
vector<int> curr2;
for(int i=(left.size()+1)/2;i<left.size();i++){
curr2.push_back(left[i]);
}
if(q(curr,right)==1){
left = curr;
}
else{
left = curr2;
}
}
assert(left.size()==1&&right.size()==1);
road(left[0],right[0]);
merge(left[0],right[0]);
}
void run(int n){
srand(55759392480137442);
for(int i=0;i<color.size();i++){
comp[i].clear();
comp[i].push_back(i);
color[i] = i;
}
vector<int> rands;
for(int i=0;i<10;i++){
rands.push_back(i);
}
for(int i=0;i<n-1;i++){
vector<int> current;
for(int j=1;j<=n;j++){
if(comp[j].size()!=0){
current.push_back(j);
}
}
random_shuffle(rands.begin(),rands.end());
for(int ii=0;ii<rands.size();ii++){
vector<int> a,b;
for(int j=0;j<current.size();j++){
if((1<<rands[ii])&j){
a.push_back(current[j]);
}
else{
b.push_back(current[j]);
}
}
if(qcomp(a,b)==1){
binarysearch(a,b);
goto cont;
}
}
assert(1==0);
cont : ;
}
}
Compilation message
icc.cpp: In function 'void merge(int, int)':
icc.cpp:44:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<color.size();i++){
~^~~~~~~~~~~~~
icc.cpp: In function 'void binarysearch(std::vector<int>, std::vector<int>)':
icc.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<(left.size()+1)/2;i++){
~^~~~~~~~~~~~~~~~~~
icc.cpp:72:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=(left.size()+1)/2;i<left.size();i++){
~^~~~~~~~~~~~
icc.cpp:85:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<(left.size()+1)/2;i++){
~^~~~~~~~~~~~~~~~~~
icc.cpp:89:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=(left.size()+1)/2;i<left.size();i++){
~^~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:104:28: warning: large integer implicitly truncated to unsigned type [-Woverflow]
srand(55759392480137442);
^
icc.cpp:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<color.size();i++){
~^~~~~~~~~~~~~
icc.cpp:122:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int ii=0;ii<rands.size();ii++){
~~^~~~~~~~~~~~~
icc.cpp:124:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<current.size();j++){
~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
512 KB |
Ok! 103 queries used. |
| 2 |
Correct |
6 ms |
512 KB |
Ok! 97 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
36 ms |
512 KB |
Ok! 536 queries used. |
| 2 |
Correct |
45 ms |
576 KB |
Ok! 661 queries used. |
| 3 |
Correct |
45 ms |
512 KB |
Ok! 672 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
129 ms |
568 KB |
Ok! 1470 queries used. |
| 2 |
Correct |
157 ms |
512 KB |
Ok! 1669 queries used. |
| 3 |
Correct |
146 ms |
572 KB |
Ok! 1652 queries used. |
| 4 |
Correct |
134 ms |
512 KB |
Ok! 1530 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
140 ms |
512 KB |
Ok! 1551 queries used. |
| 2 |
Correct |
136 ms |
512 KB |
Ok! 1523 queries used. |
| 3 |
Correct |
146 ms |
512 KB |
Ok! 1634 queries used. |
| 4 |
Correct |
133 ms |
512 KB |
Ok! 1543 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
153 ms |
512 KB |
Ok! 1634 queries used. |
| 2 |
Correct |
158 ms |
760 KB |
Ok! 1647 queries used. |
| 3 |
Correct |
151 ms |
572 KB |
Ok! 1661 queries used. |
| 4 |
Correct |
147 ms |
512 KB |
Ok! 1583 queries used. |
| 5 |
Correct |
141 ms |
632 KB |
Ok! 1502 queries used. |
| 6 |
Correct |
147 ms |
572 KB |
Ok! 1576 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
151 ms |
512 KB |
Too many queries! 1662 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
