#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int n;
bool tree[101];
vector<int> in;
vector<int> out;
typedef pair<int,int> P;
vector<P> edge;
int ind=1;
int temp1[101];
int temp2[101];
bool isedge[101][101];
/*bool query(int asz,int bsz,int a[],int b[]) {
for(int i=0;i<asz;i++) {
for(int j=0;j<bsz;j++) {
if (isedge[a[i]][b[j]]) {
return true;
}
}
}
return false;
}
void setRoad(int u,int v){
if (!isedge[u][v]) {
printf("No Road\n");
exit(0);
}
printf("%d %d\n",u,v);
if (ind==edge.size()) {
return;
}
isedge[edge[ind].first][edge[ind].second]=true;
isedge[edge[ind].second][edge[ind].first]=true;
ind++;
}*/
int p[101];
int find(int a) {
return p[a]<0?a:p[a]=find(p[a]);
}
void merge(int a,int b) {
a=find(a);
b=find(b);
if (a==b) {
return;
}
p[b]=a;
}
bool que(vector<int> one,vector<int> two) {
for(int i=0;i<one.size();i++) {
temp1[i]=one[i];
}
for(int i=0;i<two.size();i++) {
temp2[i]=two[i];
}
if (one.empty()||two.empty()) {
return false;
}
return query(one.size(),two.size(),temp1,temp2);
}
P f3() {
int xo=0; //a^b
for(int bit=0;bit<7;bit++) {
vector<int> one;
vector<int> two;
for(int i=1;i<=n;i++) {
if (tree[i]) {
if (find(i)&(1<<bit)) {
one.push_back(i);
}
else {
two.push_back(i);
}
}
}
if (que(one,two)) {
xo+=(1<<bit);
}
}
vector<int> one;
vector<int> two;
if (xo==0) {
return P(-1,-1);
}
for(int i=1;i<=n;i++) {
if (!tree[i]) {
continue;
}
int nt=(find(i)^xo);
if (nt<1||nt>n) {
continue;
}
if (find(nt)!=nt) {
continue;
}
if (find(i)<nt) {
one.push_back(i);
}
else {
two.push_back(i);
}
}
int l=0;
int r=two.size()-1;
while (l<r) {
int mid=(l+r)/2;
vector<int> temp;
for(int i=l;i<=mid;i++) {
temp.push_back(two[i]);
}
if (que(one,temp)) {
r=mid;
}
else {
l=mid+1;
}
}
int got1=two[l];
l=0;
r=one.size()-1;
while (l<r) {
int mid=(l+r)/2;
vector<int> temp;
for(int i=l;i<=mid;i++) {
temp.push_back(one[i]);
}
if (que(temp,two)) {
r=mid;
}
else {
l=mid+1;
}
}
return P(one[l],got1);
}
P f1() {
P got=f3();
if (got.first!=-1) {
return got;
}
int xo=0; //a^b
for(int bit=0;bit<7;bit++) {
vector<int> one;
vector<int> two;
for(int i=1;i<=n;i++) {
if (!tree[i]) {
if (i&(1<<bit)) {
one.push_back(i);
}
else {
two.push_back(i);
}
}
}
if (que(one,two)) {
xo+=(1<<bit);
}
}
vector<int> one;
vector<int> two;
for(int i=1;i<=n;i++) {
if (tree[i]) {
continue;
}
int nt=(i^xo);
if (nt<=n&&!tree[nt]&&i<nt) {
one.push_back(i);
}
if (nt<=n&&!tree[nt]&&i>nt) {
two.push_back(i);
}
}
int l=0;
int r=two.size()-1;
while (l<r) {
int mid=(l+r)/2;
vector<int> temp;
for(int i=l;i<=mid;i++) {
temp.push_back(two[i]);
}
if (que(one,temp)) {
r=mid;
}
else {
l=mid+1;
}
}
return P(two[l],two[l]^xo);
}
P f2() {
int l=0;
int r=in.size()-1;
while (l<r) {
int mid=(l+r)/2;
vector<int> temp;
for(int i=l;i<=mid;i++) {
temp.push_back(in[i]);
}
if (que(temp,out)) {
r=mid;
}
else {
l=mid+1;
}
}
int one=in[l];
l=0;
r=out.size()-1;
while (l<r) {
int mid=(l+r)/2;
vector<int> temp;
for(int i=l;i<=mid;i++) {
temp.push_back(out[i]);
}
if (que(in,temp)) {
r=mid;
}
else {
l=mid+1;
}
}
int two=out[l];
return P(one,two);
}
void run(int nn) {
memset(p,-1,sizeof(p));
n=nn;
for(int i=0;i<n-1;i++) {
in.clear();
out.clear();
for(int j=1;j<=n;j++) {
if (tree[j]) {
in.push_back(j);
}
else {
out.push_back(j);
}
}
P got;
if (que(in,out)) {
got=f2();
}
else {
got=f1();
}
setRoad(got.first,got.second);
merge(got.first,got.second);
tree[got.first]=true;
tree[got.second]=true;
}
}
/*int main(void) {
int n;
scanf("%d",&n);
for(int i=1;i<n;i++) {
int u,v;
scanf("%d %d",&u,&v);
edge.push_back(P(u,v));
}
isedge[edge[0].first][edge[0].second]=true;
isedge[edge[0].second][edge[0].first]=true;
run(n);
}*/
Compilation message
icc.cpp: In function 'bool que(std::vector<int>, std::vector<int>)':
icc.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i=0;i<one.size();i++) {
| ~^~~~~~~~~~~
icc.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<two.size();i++) {
| ~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
468 KB |
Ok! 111 queries used. |
| 2 |
Correct |
5 ms |
468 KB |
Ok! 109 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
468 KB |
Ok! 675 queries used. |
| 2 |
Correct |
34 ms |
496 KB |
Ok! 624 queries used. |
| 3 |
Correct |
36 ms |
480 KB |
Ok! 641 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
161 ms |
496 KB |
Ok! 1723 queries used. |
| 2 |
Correct |
118 ms |
492 KB |
Ok! 1559 queries used. |
| 3 |
Correct |
119 ms |
496 KB |
Ok! 1645 queries used. |
| 4 |
Correct |
124 ms |
492 KB |
Ok! 1678 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
148 ms |
628 KB |
Ok! 1672 queries used. |
| 2 |
Correct |
134 ms |
512 KB |
Ok! 1686 queries used. |
| 3 |
Correct |
110 ms |
496 KB |
Ok! 1579 queries used. |
| 4 |
Correct |
124 ms |
468 KB |
Ok! 1666 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
116 ms |
484 KB |
Ok! 1593 queries used. |
| 2 |
Correct |
109 ms |
496 KB |
Ok! 1566 queries used. |
| 3 |
Correct |
120 ms |
620 KB |
Ok! 1596 queries used. |
| 4 |
Correct |
152 ms |
492 KB |
Ok! 1621 queries used. |
| 5 |
Correct |
126 ms |
500 KB |
Ok! 1734 queries used. |
| 6 |
Correct |
131 ms |
492 KB |
Ok! 1655 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
116 ms |
500 KB |
Ok! 1583 queries used. |
| 2 |
Correct |
113 ms |
500 KB |
Ok! 1560 queries used. |
