This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> comp;
vector<vector<int>> nums;
int loga(int x){
int cnt=0;
while((1<<(cnt+1))<=x)
cnt++;
return cnt;
}
int buscaComp(vector<pair<int, int>> &maybe){
int l=0, r=maybe.size()-1;
while(l<r){
int mid=(l+r)/2;
int ar1[101], ar2[101];
int p1=0, p2=0;
for(int i=l; i<=mid; i++){
for(int x: nums[comp[maybe[i].first]])
ar1[p1++]=x;
for(int x: nums[comp[maybe[i].second]])
ar2[p2++]=x;
}
if(query(p1, p2, ar1, ar2))
r=mid;
else
l=mid+1;
}
return l;
}
int buscaNode(int c1, int c2){
int p2=0;
int ar2[101];
for(int x: nums[comp[c2]])
ar2[p2++]=x;
int l=0, r=nums[comp[c1]].size()-1;
while(l<r){
int mid=(l+r)/2;
int p1=0;
int ar1[101];
for(int i=l; i<=mid; i++)
ar1[p1++]=nums[comp[c1]][i];
if(query(p1, p2, ar1, ar2))
r=mid;
else
l=mid+1;
}
return nums[comp[c1]][l];
}
void buscaAri(){
int logn= loga(comp.size());
int w=0;
for(int k=0; k<logn; k++){
int p1=0, p2=0;
int ar1[101], ar2[101];
for(int i=0; i<comp.size(); i++){
if((1<<k)&i){
for(int x: nums[comp[i]])
ar1[p1++]=x;
}
else{
for(int x: nums[comp[i]])
ar2[p2++]=x;
}
}
if(query(p1, p2, ar1, ar2))
w|=(1<<k);
}
vector<pair<int, int>> maybe;
for(int i=0; i<comp.size(); i++){
int j=j^i;
if(i<j && j<comp.size()){
maybe.push_back({i, j});
}
}
int pos=buscaComp(maybe);
int c1=maybe[pos].first, c2=maybe[pos].second;
int a=0, b=0;
a=buscaNode(c1, c2);
b=buscaNode(c2, c1);
comp.erase(comp.begin()+c2);
for(int x: nums[comp[c2]])
nums[comp[c1]].push_back(x);
setRoad(a, b);
}
void run(int N){
n=N;
nums.clear();
comp.clear();
nums.resize(n+1);
for(int i=1; i<=n; i++){
nums[i].push_back(i);
comp.push_back(i);
}
for(int i=0; i<n-1; i++){
buscaAri();
}
}
Compilation message (stderr)
icc.cpp: In function 'void buscaAri()':
icc.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i=0; i<comp.size(); i++){
| ~^~~~~~~~~~~~
icc.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0; i<comp.size(); i++){
| ~^~~~~~~~~~~~
icc.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if(i<j && j<comp.size()){
| ~^~~~~~~~~~~~
icc.cpp:78:16: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
78 | int j=j^i;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |