| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605796 |
2022-07-26T02:26:11 Z |
farhan132 |
ICC (CEOI16_icc) |
C++17 |
|
2 ms |
468 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
ll Q(vector < ll > a, vector < ll > b){
if(min(a.size(), b.size()) == 0) return 0;
ll sz1 = a.size(); ll A[sz1];
ll sz2 = b.size(); ll B[sz2];
for(ll i = 0; i < sz1; i++) A[i] = a[i];
for(ll i = 0; i < sz2; i++) B[i] = b[i];
return query(sz1,sz2,A,B);
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct DSU{
vector < int > par;
void start(int n){
par.resize(n + 1);
for(int i = 0; i <= n; i++) par[i] = i;
}
int find(int a){
if(a == par[a]) return a;
return par[a] = find(par[a]);
}
void merge(int x, int y){
x = find(x); y = find(y);
if(x == y) return;
if(rng()&1) swap(x,y);
par[x] = y;
return;
}
}T;
void run(int n) {
T.start(n);
for(ll itr = 1; itr < n; itr++){
vector < ll > bit = {0,1,2,3,4,5,6};
//shuffle(bit.begin(), bit.end(), rng);
vector < ll > A,B;
vector < ll > idx;
for(ll i = 1; i <= n; i++){
idx.pb(T.find(i));
}
sort(idx.begin(), idx.end());
idx.erase(unique(idx.begin(), idx.end()), idx.end());
vector < ll > p(idx.size());
for(ll i = 0; i < p.size(); i++) p[i] = i;
shuffle(p.begin(), p.end(), rng);
ll xr = 0;
vector < ll > _A, _B;
for(auto j : bit){
A.clear();
B.clear();
for(ll i = 1; i <= n; i++){
ll k = lower_bound(idx.begin(), idx.end(), T.find(i)) - idx.begin();
k = p[k];
if((k >> j)&1) A.pb(i);
else B.pb(i);
}
if(Q(A,B)){
_A = A;
_B = B;
xr |= (1 << j);
}
}
A = _A;
B = _B;
if(B.size() > A.size()) swap(A,B);
while(A.size() > 1){
shuffle(A.begin(), A.end(), rng);
ll m = A.size()/2;
vector < ll > v1, v2;
for(ll i = 0; i < m; i++) v1.pb(A[i]);
for(ll i = m; i < A.size(); i++) v2.pb(A[i]);
if(Q(v1, B)) A = v1;
else A = v2;
}
_B.clear();
for(ll i = 1; i <= n; i++){
ll k = lower_bound(idx.begin(), idx.end(), T.find(i)) - idx.begin();
k = p[k];
if(A[0] ^ xr == p[k]) _B.pb(i);
}
B = _B;
while(B.size() > 1){
ll m = B.size()/2;
shuffle(B.begin(), B.end(), rng);
vector < ll > v1, v2;
for(ll i = 0; i < m; i++) v1.pb(B[i]);
for(ll i = m; i < B.size(); i++) v2.pb(B[i]);
if(Q(A, v1)) B = v1;
else B = v2;
}
setRoad(A[0], B[0]);
T.merge(A[0], B[0]);
}
}
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:62:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(ll i = 0; i < p.size(); i++) p[i] = i;
| ~~^~~~~~~~~~
icc.cpp:89:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(ll i = m; i < A.size(); i++) v2.pb(A[i]);
| ~~^~~~~~~~~~
icc.cpp:97:20: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
97 | if(A[0] ^ xr == p[k]) _B.pb(i);
icc.cpp:105:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(ll i = m; i < B.size(); i++) v2.pb(B[i]);
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
The query sets must be disjoint |
| 2 |
Halted |
0 ms |
0 KB |
- |
