| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 707213 |
2023-03-08T15:23:39 Z |
minhcool |
ICC (CEOI16_icc) |
C++17 |
|
134 ms |
588 KB |
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, rt[N], sz[N];
int root(int x){
return (x == rt[x] ? x : rt[x] = root(rt[x]));
}
int arr1[N], arr2[N];
/*
bool query(int a, int b, int c[], int d[]){
cout << a << " " << b << '\n';
for(int i = 0; i < a; i++) cout << c[i] << " ";
cout << "\n";
for(int i = 0; i < b; i++) cout << d[i] << " ";
cout << "\n";
int val;
cin >> val;
return val;
}*/
/*
void setRoad(int x, int y){
cout << "ADDING " << x << " " << y << '\n';
}*/
bool queryy(vector<int> a, vector<int> b){
if(!a.size() || !b.size()) return 0;
for(auto it : a) if(!it) return 0;
for(auto it : b) if(!it) return 0;
for(int i = 0; i < a.size(); i++) arr1[i] = a[i];
for(int i = 0; i < b.size(); i++) arr2[i] = b[i];
//cout << "OK\n";
return query(a.size(), b.size(), arr1, arr2);
}
void merge(int x, int y){
x = root(x), y = root(y);
assert(x != y);
if(sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
rt[y] = x;
}
void solvee(vector<int> a, vector<int> b){// conected component
assert(a.size() && b.size());
for(auto it : a) assert(it);
for(auto it : b) assert(it);
int le = 0, ri = a.size() - 1;
while(le < ri){
int mid = (le + ri) >> 1;
vector<int> temp;
for(int i = 0; i <= mid; i++) temp.pb(a[i]);
if(!queryy(temp, b)) le = mid + 1;
else ri = mid;
}
//int val1 = a[le], tempo = (le >> indd) ^ 1;
int val1 = a[le];
le = 0, ri = b.size() - 1;
while(le < ri){
int mid = (le + ri) >> 1;
vector<int> temp;
for(int i = 0; i <= mid; i++) temp.pb(b[i]);
if(!queryy(a, temp)) le = mid + 1;
else ri = mid;
}
int val2 = b[le];
merge(val1, val2);
setRoad(val1, val2);
}
int ind[N];
mt19937 rng(7405);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
bool ck1[N], ck2[N];
void run(int N){
n = N;
for(int i = 1; i <= n; i++){
rt[i] = i;
sz[i] = 1;
}
int temp = n - 1;
while(temp--){
vector<int> v;
for(int i = 1; i <= n; i++) if(root(i) == i) v.pb(i);
random_shuffle(v.begin(), v.end());
for(int i = 0; i < v.size(); i++) ind[v[i]] = i;
vector<int> a, b;
int indd = 7;
for(int i = 6; i >= 0; i--){
//cout << i << "\n";
a.clear(), b.clear();
for(int j = 1; j <= n; j++){
if(ind[root(j)] & (1LL << i)) a.pb(j);
else b.pb(j);
}
if(queryy(a, b)){
//cout << "OKAY\n";
indd = i;
break;
}
}
a.clear(), b.clear();
for(int i = 0; i < v.size(); i++){
if(i & (1LL << indd)) a.pb(v[i]);
else b.pb(v[i]);
}
/*
for(auto it : c){
for(auto it2 : d){
vector<int> x, y;
x.pb(it), y.pb(it2);
if(queryy(x, y)){
merge(it, it2);
setRoad(it, it2);
break;
}
}
}*/
/*
cout << "TEMP\n";
for(auto it : a) cout << it << " ";
cout << "\n";
for(auto it : b) cout << it << " ";
cout << "\n";*/
int le = 0, ri = a.size() - 1;// first position to be correct
while(le < ri){
int mid = (le + ri) >> 1;
vector<int> temp1, temp2;
for(int i = 1; i <= n; i++) ck1[i] = ck2[i] = 0;
for(int i = 0; i <= mid; i++) ck1[a[i]] = 1;
for(int i = 0; i < b.size(); i++) ck2[b[i]] = 1;
for(int i = 1; i <= n; i++){
if(ck1[root(i)]) temp1.pb(i);
if(ck2[root(i)]) temp2.pb(i);
}
//for(int i = 0; i <= mid; i++) temp.pb(a[i]);
if(!queryy(temp1, temp2)) le = mid + 1;
else ri = mid;
}
vector<int> c;
for(auto it : b){
int x = (it >> indd), y = (a[le] >> indd);
if(x == (y ^ 1)) c.pb(it);
}
//b = c;
//int val1 = a[le], tempo = (le >> indd) ^ 1;
int val1 = a[le];
le = 0, ri = b.size() - 1;
while(le < ri){
int mid = (le + ri) >> 1;
vector<int> temp1, temp2;
for(int i = 1; i <= n; i++) ck1[i] = ck2[i] = 0;
for(int i = 0; i <= mid; i++) ck2[b[i]] = 1;
for(int i = 0; i < a.size(); i++) ck1[a[i]] = 1;
for(int i = 1; i <= n; i++){
if(ck1[root(i)]) temp1.pb(i);
if(ck2[root(i)]) temp2.pb(i);
}
//for(int i = 0; i <= mid; i++) temp.pb(b[i]);
if(!queryy(temp1, temp2)) le = mid + 1;
else ri = mid;
}
int val2 = b[ri];
vector<int> v1, v2;
for(int i = 1; i <= n; i++){
if(root(i) == val1) v1.pb(i);
if(root(i) == val2) v2.pb(i);
}
//bool done = 0;
/*
for(auto it : v1){
if(done) break;
for(auto it2 : v2){
vector<int> x, y;
x.pb(it), y.pb(it2);
if(queryy(x, y)){
merge(it, it2);
setRoad(it, it2);
done = 1;
break;
}
}
}*/
assert(v1.size() && v2.size());
solvee(v1, v2);
//cout << "OKAY " << val1 << " " << val2 << "\n";
//solvee(v1, v2);*/
}
}
/*
void process(){
int n;
cin >> n;
run(n);
}
signed main(){
//ios_base::sync_with_stdio(0);
//cin.tie(0);
process();
}*/
Compilation message
icc.cpp:18:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
18 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
icc.cpp: In function 'bool queryy(std::vector<int>, std::vector<int>)':
icc.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i = 0; i < a.size(); i++) arr1[i] = a[i];
| ~~^~~~~~~~~~
icc.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < b.size(); i++) arr2[i] = b[i];
| ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:112:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int i = 0; i < v.size(); i++) ind[v[i]] = i;
| ~~^~~~~~~~~~
icc.cpp:129:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
icc.cpp:157:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for(int i = 0; i < b.size(); i++) ck2[b[i]] = 1;
| ~~^~~~~~~~~~
icc.cpp:180:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int i = 0; i < a.size(); i++) ck1[a[i]] = 1;
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
540 KB |
Ok! 117 queries used. |
| 2 |
Correct |
5 ms |
548 KB |
Ok! 115 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
468 KB |
Ok! 678 queries used. |
| 2 |
Correct |
33 ms |
468 KB |
Ok! 638 queries used. |
| 3 |
Correct |
36 ms |
544 KB |
Ok! 717 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
544 KB |
Ok! 1792 queries used. |
| 2 |
Correct |
131 ms |
528 KB |
Ok! 1608 queries used. |
| 3 |
Correct |
130 ms |
556 KB |
Ok! 1982 queries used. |
| 4 |
Correct |
131 ms |
588 KB |
Ok! 1892 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
536 KB |
Ok! 1927 queries used. |
| 2 |
Correct |
130 ms |
540 KB |
Ok! 1927 queries used. |
| 3 |
Correct |
134 ms |
468 KB |
Ok! 1925 queries used. |
| 4 |
Correct |
125 ms |
556 KB |
Ok! 1896 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
130 ms |
544 KB |
Too many queries! 1855 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
560 KB |
Too many queries! 1844 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
