| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 96001 |
2019-02-05T05:27:30 Z |
youngyojun |
ICC (CEOI16_icc) |
C++11 |
|
2 ms |
632 KB |
#include "icc.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
typedef pair<int, int> pii;
mt19937 mtrd(time(0));
int askA[105], askB[105];
bool ask(vector<int> &A, vector<int> &B) {
int a = 0, b = 0;
for(int v : A) askA[a++] = v;
for(int v : B) askB[b++] = v;
return query(a, b, askA, askB);
}
vector<int> UV[105];
int ud[105];
int N;
int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
void uf(int a, int b) {
a = uf(a); b = uf(b);
if(a == b) return;
for(int v : UV[b]) UV[a].eb(v);
UV[b].clear();
ud[b] = a;
}
void run() {
vector<int> LV;
for(int i = 1; i <= N; i++)
if(uf(i) == i) LV.eb(i);
shuffle(allv(LV), mtrd);
int n = sz(LV), x = 0;
for(int k = 1;; k <<= 1) {
bool flag = false;
for(int i = 0; i < n; i++) {
if(n <= (i^x^k)) continue;
flag = true;
break;
}
if(flag) break;
vector<int> AV, BV;
for(int i = 0; i < n; i++) {
auto &V = (i&k) ? AV : BV;
for(int v : UV[LV[i]]) V.eb(v);
}
if(AV.empty() || BV.empty()) continue;
if(ask(AV, BV)) x |= k;
}
vector<pii> EV;
for(int i = 0, j; i < n; i++) {
j = i^x;
if(j <= i || n <= j) continue;
EV.eb(i, j);
}
shuffle(allv(EV), mtrd);
for(; 1 < sz(EV);) {
vector<pii> LE, RE;
int e = sz(EV), m = e >> 1;
for(int i = 0; i < m; i++) LE.eb(EV[i]);
for(int i = m; i < e; i++) RE.eb(EV[i]);
vector<int> AV, BV;
for(auto &ed : LE) {
for(int v : UV[LV[ed.first]]) AV.eb(v);
for(int v : UV[LV[ed.second]]) BV.eb(v);
}
swap(EV, ask(AV, BV) ? LE : RE);
}
vector<int> AT, BT;
for(int v : UV[LV[EV[0].first]]) AT.eb(v);
for(int v : UV[LV[EV[0].second]]) BT.eb(v);
shuffle(allv(AT), mtrd);
shuffle(allv(BT), mtrd);
for(; 1 < sz(AT);) {
vector<int> AL, AR;
int e = sz(AT), m = e >> 1;
for(int i = 0; i < m; i++) AL.eb(AT[i]);
for(int i = m; i < e; i++) AR.eb(AT[i]);
swap(AT, ask(AL, BT) ? AL : AR);
}
for(; 1 < sz(BT);) {
vector<int> BL, BR;
int e = sz(BT), m = e >> 1;
for(int i = 0; i < m; i++) BL.eb(BT[i]);
for(int i = m; i < e; i++) BR.eb(BT[i]);
swap(BT, ask(AT, BL) ? BL : BR);
}
{
int a = AT[0], b = BT[0];
uf(a, b);
setRoad(a, b);
}
}
void run(int _N) {
N = _N;
iota(ud, ud+N+1, 0);
for(int i = 1; i <= N; i++) UV[i].eb(i);
for(int lq = 1; lq < N; lq++) run();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
