Submission #1031199

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1031199	2024-07-22T16:01:23 Z	MarwenElarbi	cmp (balkan11_cmp)	C++17	46 / 100	2328 ms	105036 KB

cmp

#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;
      |        ~^~~~~~~~~~~~

Subtask #1

46.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	2328 ms	105036 KB	Output is partially correct - maxAccess = 16, score = 46