#include <bits/stdc++.h>
#include "Anna.h"
#ifdef TEST
#define my_printf printf
#else
void my_printf(const char* s, ...){
}
#endif // TEST
using namespace std;
typedef long long ll;
namespace Anna{
int n, l, r, m;
int firstVertex, firstL, firstR, depth;
int turnsLeft = 18;
int arr[1000002];
int binaryL, binaryR, binaryM;
int nowL, nowR;
int start, len;
int notIncludeL, notIncludeR;
vector<bool> finalInfo;
vector<int> link[1000002];
int par[1000002];
int minCover(int x){
for(int i=1; i<=30; i++) if(x <= (1<<i)) return i;
exit(1);
}
void InitA(int N, int L, int R){
n = N, l = L, r = R;
n = 1000000;
firstVertex = 0, firstL = 0, firstR = n-1;
while(depth < 13){
int m = (firstL + firstR) / 2;
if(r <= m){
firstVertex *= 2;
depth++;
firstR = m;
}
else if(l > m){
firstVertex = firstVertex * 2 + 1;
depth++;
firstL = m;
}
else break;
}
if(depth <= 1){
SendA(0);
SendA(0);
SendA(depth);
turnsLeft -= 3;
}
else{
depth += 2;
SendA(!!(depth & 8));
SendA(!!(depth & 4));
SendA(!!(depth & 2));
SendA(!!(depth & 1));
turnsLeft -= 4;
depth -= 2;
}
for(int i=0; i<depth; i++) SendA(!!(firstVertex & (1<<i)));
turnsLeft -= depth;
binaryL = 1;
binaryR = firstR-firstL;
binaryM = (binaryL + binaryR) / 2;
m = (firstL+firstR)/2;
nowL = firstL, nowR = firstR;
notIncludeL = m, notIncludeR = m+1;
start = 0;
len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
my_printf("Initialize Result (Anna): firstL %d, firstR %d, m %d\n", firstL, firstR, m);
}
void RecieveA(bool x){
if(!turnsLeft){
finalInfo.push_back(x);
return;
}
len--;
start = start*2+x;
if(!len){
int minAble = max(nowL, m+1-binaryM);
int p = minAble + start;
int q = p + binaryM;
my_printf("Anna: %d %d %d %d\n", nowL, nowR, notIncludeL, notIncludeR);
my_printf("Want to ask: [%d, %d] / Send: %d\n", p, q, start);
if(p <= l && r <= q){
SendA(1);
nowL = p, nowR = q;
binaryR = binaryM-1;
start = 0;
len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
}
else{
SendA(0);
notIncludeL = p, notIncludeR = q;
binaryL = binaryM+1;
start = 0;
len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
}
turnsLeft--;
}
}
void dfs(int x, int y){
arr[x] = y;
for(auto nxt: link[x]) dfs(nxt, y+1);
}
int Answer(){
int rangeMin = 0;
for(int i=0; i<20; i++) if(finalInfo[i]) rangeMin += (1<<i);
reverse(finalInfo.begin(), finalInfo.end());
for(int i=0; i<20; i++) finalInfo.pop_back();
reverse(finalInfo.begin(), finalInfo.end());
vector<int> indices;
for(int i=nowL; i<notIncludeL; i++) indices.push_back(i);
indices.push_back(rangeMin);
for(int i=notIncludeR+1; i<=nowR; i++) indices.push_back(i);
my_printf("Anna: indices size %d, finalInfo size %d\n", (int)indices.size(), (int)finalInfo.size());
for(int i=nowL; i<=nowR; i++) arr[i] = 1e9;
assert(finalInfo.size() == indices.size() * 2);
int pnt = 0;
vector<int> stk;
memset(par, -1, sizeof(par));
for(auto x: indices){
while(1){
int child = -1;
if(pnt == (int)finalInfo.size()) break;
if(finalInfo[pnt] == 1){
if(!stk.empty()) par[x] = stk.back();
stk.push_back(x);
pnt++;
break;
}
else{
if(child != -1) par[child] = stk.back();
par[stk.back()] = x, child = stk.back();
stk.pop_back();
pnt++;
}
}
}
int root = -1;
for(auto x: indices){
if(par[x] != -1) link[par[x]].push_back(x);
else root = x;
}
dfs(root, 0);
return min_element(arr+l, arr+r+1) - arr;
}
}
void InitA(int N, int L, int R){
Anna::InitA(N, L, R);
}
void ReceiveA(bool x){
Anna::RecieveA(x);
}
int Answer() {
return Anna::Answer();
}
#include <bits/stdc++.h>
#include "Bruno.h"
#ifdef TEST
#define my_printf printf
#else
void my_printf(const char* s, ...){
}
#endif // TEST
using namespace std;
typedef long long ll;
namespace Bruno{
int n;
int arr[1000002];
int l, r;
int depth, state, start, cnt;
int turnsLeft = 18;
int m, len;
int rangeL[1000002], rangeR[1000002];
int binaryL, binaryR, binaryM;
int nowL, nowR;
int notIncludeL, notIncludeR;
void InitB(int N, vector<int> P) {
n = N;
for(int i=0; i<1000000; i++){
if(i < n) arr[i] = P[i];
else arr[i] = i;
}
n = 1000000;
}
void init_binary(){
rangeL[1] = m, rangeR[1] = m+1;
for(int i=2; i<=r-l; i++){
if(rangeL[i-1] == l) rangeL[i] = l, rangeR[i] = rangeR[i-1]+1;
else if(rangeR[i-1] == r) rangeR[i] = r, rangeL[i] = rangeL[i-1]-1;
else if(arr[rangeL[i-1]-1] > arr[rangeR[i-1]+1]) rangeL[i] = rangeL[i-1]-1, rangeR[i] = rangeR[i-1];
else rangeL[i] = rangeL[i-1], rangeR[i] = rangeR[i-1]+1;
}
binaryL = 1, binaryR = r-l;
}
int minCover(int x){
for(int i=1; i<=30; i++) if(x <= (1<<i)) return i;
exit(1);
}
void ReceiveB(bool y){
bool alreadyUsed = 0;
cnt++, turnsLeft--;
if(state == 0){ /// 아직 깊이도 완성하지 못한 상태
depth = depth * 2 + y;
if(cnt == 3 && depth<=1) state = 1, cnt = 0;
else if(cnt == 4) state = 1, depth-=2, cnt = 0;
return;
}
if(state == 1){ /// 시작 정점을 입력받는 중인 상태
start = start * 2 + y;
if(depth == cnt){
state = 2, cnt = 0;
l = 0, r = n-1;
for(int i=0; i<depth; i++){
int M = (l+r) / 2;
if(start & (1<<i)) l = M+1;
else r = M;
}
m = (l+r)/2;
init_binary();
binaryL = 1;
binaryR = r-l;
binaryM = (binaryL + binaryR) / 2;
nowL = l, nowR = r;
notIncludeL = m, notIncludeR = m+1;
start = 0;
len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
alreadyUsed = 1;
state = 2;
my_printf("Initialize Result (Bruno): firstL %d, firstR %d, m %d\n", l, r, m);
}
else return;
}
if(!alreadyUsed){
if(y){ /// Bruno가 물어본 구간에 Anna의 구간이 포함된다.
nowL = rangeL[binaryM], nowR = rangeR[binaryM];
binaryR = binaryM-1;
start = 0;
len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
}
else{
notIncludeL = rangeL[binaryM], notIncludeR = rangeR[binaryM];
binaryL = binaryM+1;
start = 0;
len = minCover(min(m, nowR-binaryM) - max(nowL, m+1-binaryM) + 1);
}
}
if(turnsLeft){ /// 이분 탐색을 진행해야 하는 상태
int minAble = max(nowL, m+1-binaryM);
int val = rangeL[binaryM] - minAble;
assert(val < (1<<len));
my_printf("Bruno: %d %d %d %d\n", nowL, nowR, notIncludeL, notIncludeR);
my_printf("Want to ask: [%d, %d] / Send: %d\n", rangeL[binaryM], rangeR[binaryM], val);
for(int i=len-1; i>=0; i--) SendB(!!(val & (1<<i)));
return;
}
/// 카르테시안 트리 보내기
int rangeMin = notIncludeL;
for(int i=notIncludeL+1; i<=notIncludeR; i++){
if(arr[rangeMin] > arr[i]) rangeMin = i;
}
for(int i=0; i<20; i++) SendB(!!(rangeMin & (1<<i)));
vector<pair<int, int> > vec;
stack<int> stk;
for(int i=nowL; i<notIncludeL; i++) vec.push_back(make_pair(i, arr[i]));
vec.push_back(make_pair(rangeMin, arr[rangeMin]));
for(int i=notIncludeR+1; i<=nowR; i++) vec.push_back(make_pair(i, arr[i]));
my_printf("Bruno: vec size %d\n", (int)vec.size());
for(auto x: vec){
while(!stk.empty() && stk.top() > x.second){
stk.pop();
SendB(0);
}
stk.push(x.second);
SendB(1);
}
while(!stk.empty()){
stk.pop();
SendB(0);
}
}
}
void InitB(int N, vector<int> P){
Bruno::InitB(N, P);
}
void ReceiveB(bool x){
Bruno::ReceiveB(x);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
31796 KB |
Output is correct |
| 2 |
Correct |
20 ms |
31796 KB |
Output is correct |
| 3 |
Correct |
20 ms |
31792 KB |
Output is correct |
| 4 |
Correct |
20 ms |
31808 KB |
Output is correct |
| 5 |
Correct |
20 ms |
31920 KB |
Output is correct |
| 6 |
Correct |
26 ms |
31788 KB |
Output is correct |
| 7 |
Correct |
23 ms |
31744 KB |
Output is correct |
| 8 |
Correct |
28 ms |
31792 KB |
Output is correct |
| 9 |
Runtime error |
39 ms |
48128 KB |
Execution killed with signal 6 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
31796 KB |
Output is correct |
| 2 |
Correct |
20 ms |
31796 KB |
Output is correct |
| 3 |
Correct |
20 ms |
31792 KB |
Output is correct |
| 4 |
Correct |
20 ms |
31808 KB |
Output is correct |
| 5 |
Correct |
20 ms |
31920 KB |
Output is correct |
| 6 |
Correct |
26 ms |
31788 KB |
Output is correct |
| 7 |
Correct |
23 ms |
31744 KB |
Output is correct |
| 8 |
Correct |
28 ms |
31792 KB |
Output is correct |
| 9 |
Runtime error |
39 ms |
48128 KB |
Execution killed with signal 6 |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
47988 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
