# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
606274 |
2022-07-26T05:55:08 Z |
Jarif_Rahman |
ICC (CEOI16_icc) |
C++17 |
|
124 ms |
616 KB |
#include "icc.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
bool Query(vector<int> _A, vector<int> _B){
int a = _A.size(), b = _B.size();
int A[a], B[b];
for(int i = 0; i < a; i++) A[i] = _A[i]+1;
for(int i = 0; i < b; i++) B[i] = _B[i]+1;
return query(a, b, A, B);
}
void SetRoad(int a, int b){
setRoad(a+1, b+1);
}
void run(int n){
vector<vector<int>> comps(n);
for(int i = 0; i < n; i++) comps[i].pb(i);
for(int I = 0; I < n-1; I++){
int c = comps.size();
int k = 1, xr = 0;
while(k <= c-1){
vector<int> s0, s1;
for(int i = 0; i < c; i++){
if(i&k) for(int x: comps[i]) s1.pb(x);
else for(int x: comps[i]) s0.pb(x);
}
if(Query(s0, s1)) xr+=k;
k*=2;
}
vector<int> s;
for(int i = 0; i < c; i++){
if((i^xr) < i || (i^xr) >= c) continue;
s.pb(i);
}
int a = 0, b = int(s.size())-1;
while(a < b){
int md = (a+b)/2;
vector<int> s1, s2;
for(int i = 0; i <= md; i++){
for(int x: comps[s[i]]) s1.pb(x);
for(int x: comps[s[i]^xr]) s2.pb(x);
}
if(Query(s1, s2)) b = md;
else a = md+1;
}
int A = s[a], B = s[a]^xr;
a = 0, b = int(comps[B].size())-1;
while(a < b){
int md = (a+b)/2;
vector<int> ss(comps[B].begin(), comps[B].begin()+md+1);
if(Query(comps[A], ss)) b = md;
else a = md+1;
}
int node_b = comps[B][a];
a = 0, b = int(comps[A].size())-1;
while(a < b){
int md = (a+b)/2;
vector<int> ss(comps[A].begin(), comps[A].begin()+md+1);
if(Query(ss, {node_b})) b = md;
else a = md+1;
}
int node_a = comps[A][a];
SetRoad(node_a, node_b);
if(comps[A].size() < comps[B].size()) swap(comps[A], comps[B]);
while(!comps[B].empty()){
comps[A].pb(comps[B].back());
comps[B].pop_back();
}
comps.erase(comps.begin()+B);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
468 KB |
Ok! 109 queries used. |
2 |
Correct |
5 ms |
468 KB |
Ok! 107 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
380 KB |
Ok! 616 queries used. |
2 |
Correct |
26 ms |
496 KB |
Ok! 459 queries used. |
3 |
Correct |
25 ms |
496 KB |
Ok! 518 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
488 KB |
Ok! 1538 queries used. |
2 |
Correct |
93 ms |
504 KB |
Ok! 1077 queries used. |
3 |
Correct |
124 ms |
468 KB |
Ok! 1524 queries used. |
4 |
Correct |
106 ms |
468 KB |
Ok! 1514 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
504 KB |
Ok! 1454 queries used. |
2 |
Correct |
109 ms |
500 KB |
Ok! 1473 queries used. |
3 |
Correct |
107 ms |
488 KB |
Ok! 1481 queries used. |
4 |
Correct |
104 ms |
488 KB |
Ok! 1530 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
484 KB |
Ok! 1483 queries used. |
2 |
Correct |
93 ms |
488 KB |
Ok! 1450 queries used. |
3 |
Correct |
94 ms |
508 KB |
Ok! 1343 queries used. |
4 |
Correct |
104 ms |
468 KB |
Ok! 1492 queries used. |
5 |
Correct |
101 ms |
616 KB |
Ok! 1519 queries used. |
6 |
Correct |
99 ms |
492 KB |
Ok! 1528 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
97 ms |
588 KB |
Ok! 1444 queries used. |
2 |
Correct |
92 ms |
488 KB |
Ok! 1259 queries used. |