#include "Anna.h"
#include<bits/stdc++.h>
using namespace std;
#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 = 1e6 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int nn, l, r;
void InitA(int N, int L, int R){
nn = N, l = L, r = R;
l++, r++;
}
int cnt1 = 0, cnt2 = 0;
vector<int> lst_bits;
ii ans = {oo, oo};
void ReceiveA(bool x){
cnt1++;
lst_bits.pb(x);
//cout << cnt1 << "\n";
if(nn > 10){
if(cnt1 % 40) return;
if(cnt2 < 18){
int le = 0, ri = 0;
for(int i = 0; i < 20; i++) le = (le * 2 + lst_bits[i]);
for(int i = 0; i < 20; i++) ri = (ri * 2 + lst_bits[i + 20]);
if(le <= l && ri >= r) SendA(1);
else SendA(0);
lst_bits.clear();
cnt2++;
}
else{
int pos = 0, val = 0;
for(int i = 0; i < 20; i++) pos = (pos * 2 + lst_bits[i]);
for(int i = 0; i < 20; i++) val = (val * 2 + lst_bits[i + 20]);
if(l <= pos && pos <= r) ans = min(ans, {val, pos});
lst_bits.clear();
}
}
else{
if(cnt1 % 20) return;
int pos = (cnt1 / 20), val = 0;
for(int i = 0; i < 20; i++) val = (val * 2 + lst_bits[i]);
//cout << pos << " " << val << "\n";
if(l <= pos && pos <= r) ans = min(ans, {val, pos});
lst_bits.clear();
}
}
int Answer(){
//cout << ans.fi << " " << ans.se << "\n";
return ans.se - 1;
}
#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
#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 = 1e6 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, arr[N];
int mini[N][21];
int mn_pos(int l, int r){
int k = log2(r - l + 1);
if(arr[mini[l][k]] < arr[mini[r - (1LL << k) + 1][k]]) return mini[l][k];
else return mini[r - (1LL << k) + 1][k];
}
int cnt, par[N];
set<int> childs[N];
ii ranges[N];
int pos[N];
void build(int l, int r, int pare){
if(l > r) return;
int temp = mn_pos(l, r);
cnt++;
pos[cnt] = temp;
if(pare){
//cout << cnt << " " << pare << " " << l << " " << r << "\n";
childs[pare].insert(cnt);
par[cnt] = pare;
}
ranges[cnt] = {l, r};
int tempo = cnt;
build(l, temp - 1, tempo);
build(temp + 1, r, tempo);
}
int cur_root, cur_ask;
int sz[N];
void prep(int u){
sz[u] = 1;
for(auto v : childs[u]){
prep(v);
sz[u] += sz[v];
}
}
void sendnum(int x){
//cout << x << "\n";
for(int i = 19; i >= 0; i--){
SendB((x & (1LL << i)) != 0);
}
}
void InitB(int nn, vector<int> P){
n = nn;
///P.push_front(0);
vector<int> P2;
P2.pb(0);
for(auto it : P) P2.pb(it);
P = P2;
for(int i = 1; i <= n; i++) arr[i] = P[i];
for(int i = 1; i <= n; i++) mini[i][0] = i;
for(int i = 1; i <= 19; i++){
for(int j = 1; (j + (1LL << i) - 1) <= n; j++){
int temp1 = P[mini[j][i - 1]], temp2 = P[mini[j + (1LL << (i - 1))][i - 1]];
if(temp1 < temp2) mini[j][i] = mini[j][i - 1];
else mini[j][i] = mini[j + (1LL << (i - 1))][i - 1];
}
}
build(1, n, 0);
if(n > 10){
cur_root = 1;
for(int i = 1; i <= n; i++) sz[i] = 0;
prep(cur_root);
ii mn = {oo, oo};
for(int i = 1; i <= n; i++) mn = min(mn, {abs(sz[i] - n/2), i});
cur_ask = mn.se;
//cout << cur_ask << " " << ranges[cur_ask].fi << " " << ranges[cur_ask].se << "\n";
sendnum(ranges[mn.se].fi), sendnum(ranges[mn.se].se);
/*
cur_root = 1, cur_ask = find_cen(1);
ii mx = {-1, -1};
for(auto v : child[cur_ask]) mx = max(mx, {sz[v], v});
cur_ask = v.se;
sendnum(range[cur_ask].fi);
sendnum(range[cur_ask].se);*/
//for(int i = 0; i <= 19; i++) SendB()
}
else{
//cout << "OK\n" << n << "\n";
for(int i = 1; i <= n; i++) sendnum(P[i]);
}
}
int c = 0;
void prep2(int u){
sendnum(pos[u]);
sendnum(arr[pos[u]]);
for(auto v : childs[u]) prep2(v);
}
void ReceiveB(bool y) {
assert(n > 10);
c++;
if(!y) childs[par[cur_ask]].erase(cur_ask);
else cur_root = cur_ask;
//cout << cur_root << "\n";
if(c < 18){
for(int i = 1; i <= n; i++) sz[i] = 0;
prep(cur_root);
ii mn = {oo, oo};
for(int i = 1; i <= n; i++) mn = min(mn, {abs(sz[i] - sz[cur_root]/2), i});
for(int i = 1; i <= n; i++) cout << i << " " << sz[i] << "\n";
cur_ask = mn.se;
//cout << cur_ask << "\n";
//cout << ranges[cur_ask].fi << " " << ranges[cur_ask].se << "\n";
sendnum(ranges[mn.se].fi), sendnum(ranges[mn.se].se);
}
else{
prep2(cur_root);
}
}
/*
20 9 16
5 7 10 8 6 3 2 1 9 4 12 15 18 20 19 17 14 13 16 11
*/
Compilation message
Anna.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
Bruno.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
47480 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47504 KB |
Output is correct |
| 3 |
Correct |
24 ms |
47480 KB |
Output is correct |
| 4 |
Correct |
22 ms |
47428 KB |
Output is correct |
| 5 |
Correct |
21 ms |
47392 KB |
Output is correct |
| 6 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
47480 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47504 KB |
Output is correct |
| 3 |
Correct |
24 ms |
47480 KB |
Output is correct |
| 4 |
Correct |
22 ms |
47428 KB |
Output is correct |
| 5 |
Correct |
21 ms |
47392 KB |
Output is correct |
| 6 |
Runtime error |
1 ms |
200 KB |
Execution killed with signal 13 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
276 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
