| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 707120 |
2023-03-08T13:26:29 Z |
minhcool |
ICC (CEOI16_icc) |
C++17 |
|
157 ms |
640 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 queryy(vector<int> a, vector<int> b){
for(int i = 0; i < a.size(); i++) arr1[i] = a[i];
for(int i = 0; i < b.size(); i++) arr2[i] = b[i];
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;
}
int ind[N];
mt19937 rng(7405);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
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);
vector<int> a, b;
while(1){
a.clear(), b.clear();
shuffle(v.begin(), v.end(), default_random_engine(rnd(1, 100000)));
for(int i = 0; i < v.size(); i++) ind[v[i]] = i;
for(int i = 1; i <= n; i++){
if(ind[root(i)] < (v.size() / 2)) a.pb(i);
else b.pb(i);
}
bool ck = queryy(a, b);
if(ck) break;
}
int le = 0, ri = a.size() - 1;// first position to be correct
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];
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);
}
}
/*
void process(){
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) process();
}
*/
Compilation message
icc.cpp:17:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
17 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
icc.cpp: In function 'bool queryy(std::vector<int>, std::vector<int>)':
icc.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 0; i < a.size(); i++) arr1[i] = a[i];
| ~~^~~~~~~~~~
icc.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i = 0; i < b.size(); i++) arr2[i] = b[i];
| ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i = 0; i < v.size(); i++) ind[v[i]] = i;
| ~~^~~~~~~~~~
icc.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | if(ind[root(i)] < (v.size() / 2)) a.pb(i);
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
468 KB |
Ok! 101 queries used. |
| 2 |
Correct |
4 ms |
468 KB |
Ok! 92 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
532 KB |
Ok! 534 queries used. |
| 2 |
Correct |
43 ms |
532 KB |
Ok! 841 queries used. |
| 3 |
Correct |
41 ms |
520 KB |
Ok! 781 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
524 KB |
Ok! 1520 queries used. |
| 2 |
Correct |
157 ms |
512 KB |
Ok! 2122 queries used. |
| 3 |
Correct |
117 ms |
520 KB |
Ok! 1674 queries used. |
| 4 |
Correct |
118 ms |
468 KB |
Ok! 1688 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
115 ms |
520 KB |
Ok! 1642 queries used. |
| 2 |
Correct |
120 ms |
520 KB |
Ok! 1664 queries used. |
| 3 |
Correct |
129 ms |
516 KB |
Ok! 1825 queries used. |
| 4 |
Correct |
112 ms |
640 KB |
Ok! 1585 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
516 KB |
Too many queries! 1867 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
128 ms |
512 KB |
Too many queries! 1823 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
