oj.uz

Submission #1057322

# Submission time Handle Problem Language Result Execution time Memory
1057322 2024-08-13T17:16:20 Z shenfe1 The Big Prize (IOI17_prize) C++17
20 / 100
 64 ms 2416 KB 
#include <bits/stdc++.h>
#include "prize.h"
    
using namespace std;
    
#define pb push_back
#define pii pair<int,int>
#define sz(s) (int)s.size()
#define F first
#define S second
#define all(v) v.begin(),v.end()
    
const int MAX=2e5+10;
    
bool use[MAX];
pii res[MAX];
    
pii cnt(int pos){
    if(use[pos])return res[pos];
    use[pos]=1;
    vector<int> v=ask(pos);
    return res[pos]={v[0],v[1]};
}
    
int sum(int pos){
    pii c=cnt(pos);
    return c.F+c.S;
}
    
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
int rnd(int l,int r){
    return rng()%(r-l+1)+l;
}
    
int cntMx;
    
int find_best(int n){
    cntMx=0;
    int L=500;
    // int r=0;
    for(int j=0;j<min(n,L);j++){
        cntMx=max(cntMx,sum(j));
        // r++;
        if(sum(j)==0)return j;
        // if(cntMx>n/2)break;
    }
    // int pref=0;
    // for(int j=0;j<r;j++){
    //     if(sum(j)!=cntMx)pref++;
    // }
    queue<pair<pii,pii>>  q;
    q.push({{0,n-1},{cntMx,0}});
    while(!q.empty()){
        int l=q.front().F.F,r=q.front().F.S,c=q.front().S.F,pl=q.front().S.S;
        q.pop();
        if(c==0)continue;
        if(c==r-l+1){
            for(int i=l;i<=r;i++){
                if(sum(i)==0){
                    return i;
                }
            }
            continue;
        }
        int tl=(l+r)/2,tr=(l+r)/2;
        while(tl>=l&&sum(tl)!=cntMx){
            if(sum(tl)==0){
                return tl;
            }
            tl--;
        }
        while(tr<=r&&sum(tr)!=cntMx){
            if(sum(tr)==0){
                return tr;
            }
            tr++;
        }
        if(tl>=0){
            int L=cnt(tl).F-pl;
            if(l<=tl-1)q.push({{l,tl-1},{L,pl}});
        }
        if(tr<n){
            int R=c-cnt(tr).F;
            if(tr+1<=r){
                q.push({{tr+1,r},{R,cnt(tr).F}});
            }
        }
    }
    return -1;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 3 ms 440 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 344 KB Output is correct
11 Correct 6 ms 1368 KB Output is correct
12 Correct 8 ms 1476 KB Output is correct
13 Correct 6 ms 1368 KB Output is correct
14 Correct 8 ms 600 KB Output is correct
15 Partially correct 42 ms 2392 KB Partially correct - number of queries: 9650
16 Partially correct 59 ms 2136 KB Partially correct - number of queries: 9147
17 Correct 1 ms 344 KB Output is correct
18 Partially correct 33 ms 2220 KB Partially correct - number of queries: 7538
19 Correct 2 ms 344 KB Output is correct
20 Partially correct 26 ms 1356 KB Partially correct - number of queries: 6561
21 Partially correct 22 ms 2136 KB Partially correct - number of queries: 6418
22 Partially correct 64 ms 2216 KB Partially correct - number of queries: 9518
23 Correct 3 ms 852 KB Output is correct
24 Correct 6 ms 1368 KB Output is correct
25 Partially correct 37 ms 2416 KB Partially correct - number of queries: 9606
26 Incorrect 39 ms 2168 KB Incorrect
27 Halted 0 ms 0 KB -