#include <bits/stdc++.h>
using namespace std;
#define se second
#define fi first
/*unsigned char boiMem[4096][10248];
int boiOrder[16777216];
int boiAccesses;
int boiPhase;
int boi_guessval;
int boi_cmpval;
int boi_storeval;
void bit_set(int addr)
{
if(boiPhase == 2) {
fprintf(stderr, "ZERO POINTS: bit_set called by compare()\n");
exit(1);
}
if((addr > 10240) || (addr < 1)) {
fprintf(stderr, "ZERO POINTS: bit_set with addr out of range %d\n", addr);
exit(1);
}
boiMem[boi_storeval][addr] |= 1;
boiAccesses++;
if(boiAccesses > 20) {
fprintf(stderr, "ERROR: bit_set called more than 20 times\n");
exit(1);
}
}
int bit_get(int addr)
{
if(boiPhase == 1) {
fprintf(stderr, "ZERO POINTS: bit_get called by remember()\n");
exit(1);
}
boiAccesses++;
if((addr > 10240) || (addr < 1)) {
fprintf(stderr, "ZERO POINTS: bit_get with address out of range\n");
exit(1);
}
return boiMem[boi_guessval][addr]?1:0;
}*/
void bit_set(int addr);
int bit_get(int addr);
void build(int pos,int l,int r,int idx){
if(pos>1) bit_set(pos);
if(l==r) return;
int mid=(r+l)/2;
if(idx<=mid) build(pos*2,l,mid,idx);
else build(pos*2+1,mid+1,r,idx);
return;
}
void remember(int n) {
build(1,0,(1<<12)-1,n);
}
vector<pair<int,pair<int,int>>> cur;
void get(int pos,int l,int r,int idx){
if(pos>1) cur.push_back({pos,{l,r}});
if(l==r) return;
int mid=(r+l)/2;
if(idx<=mid) get(pos*2,l,mid,idx);
else get(pos*2+1,mid+1,r,idx);
return;
}
int compare(int b){
cur.clear();
cur.push_back({1,{0,(1<<12)-1}});
get(1,0,(1<<12)-1,b);
int l=0;
int r=cur.size();
while(r-l>1){
int mid=(r+l)/2;
if(bit_get(cur[mid].fi)) l=mid;
else r=mid;
}
if(r==cur.size()) return 0;
else if(b>(cur[l].se.fi+cur[l].se.se)/2) return 1;
else return -1;
}
/*
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int maxa = 0, maxb = 0, x, y, i;
int N;
cin >> N;
boiPhase = 1;
for(boi_storeval = 0; boi_storeval < N; boi_storeval++) {
boiAccesses =0;
remember(boi_storeval);
if(boiAccesses > maxa)
maxa = boiAccesses;
}
boiPhase = 3;
for (i=0; i<16777216; i++) boiOrder[i]=i;
srand(2);
for (i=1; i<16777216; i++) {
int t=rand();
if(RAND_MAX<=32768)t=t*32768+rand();
x=t%i;
y=boiOrder[i];
boiOrder[i]=boiOrder[x];
boiOrder[x]=y;
}
srand(2);
for (i=0; i<16777216; i++) {
boi_guessval=boiOrder[i] % N;
boi_cmpval =boiOrder[i] / N;
boiAccesses=0;
x=compare(boi_cmpval);
y=0;
if (boi_cmpval>boi_guessval)
y=1;
if (boi_cmpval<boi_guessval)
y=-1;
if (x!=y) {
fprintf(stderr, "ZERO POINTS: For a=%d and b=%d, correct answer is %d, got %d\n",boi_guessval,boi_cmpval,y,x);
exit(1);
}
if (boiAccesses>maxb)
maxb=boiAccesses;
}
boiPhase=2;
x=maxa+maxb;
if (x>20)
fprintf(stderr, "ZERO POINTS: more than 20 accesses in the worst case\n");
fprintf(stderr, "maxAccesses = %d\n", x);
return 0;
}
*/
Compilation message
cmp.cpp: In function 'int compare(int)':
cmp.cpp:78:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if(r==cur.size()) return 0;
| ~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Partially correct |
2328 ms |
105036 KB |
Output is partially correct - maxAccess = 16, score = 46 |
