oj.uz

Submission #782144

# Submission time Handle Problem Language Result Execution time Memory
782144 2023-07-13T15:37:53 Z Khizri The Big Prize (IOI17_prize) C++17
0 / 100
 6 ms 1904 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxn=2e5+5;
int n,l[mxn],r[mxn],color[mxn],tree[mxn],p[mxn];
void update(int idx,int val){
    while(idx<=n){
        tree[idx]+=val;
        idx+=(idx&(-idx));
    }
}
int query(int l,int r){
    if(l!=1){
        return query(1,r)-query(1,l-1);
    }
    int idx=r;
    int ans=0;
    while(idx>0){
        ans+=tree[idx];
        idx-=(idx&(-idx));
    }
    return ans;
}
pii fnd(int idx){
    if(l[idx]!=-1){
        return {l[idx],r[idx]};
    }
    vector<int>res=ask(idx);
    l[idx]=res[0];
    r[idx]=res[1];
    return {res[0],res[1]};
}
pii funk(int idx){
    int l=idx,r=idx;
    while(l>0&&p[l]==1) l--;
    while(r<n&&p[r]==1) r++;
    return {l,r};
}
int find_best(int N) {
    n=N;
	memset(l,-1,sizeof(l));
	memset(r,-1,sizeof(r));
	int qq=448;
	int mx=0;
	while(qq--){
        int idx=rng()%n;
        if(l[idx]!=-1){
            qq++;
            continue;
        }
        vector<int> res = ask(idx);
        l[idx]=res[0];
        r[idx]=res[1];
        if(l[idx]+r[idx]==0) return idx;
        mx=max(mx,l[idx]+r[idx]);
	}
	int cnt=mx;
	int qw=cnt;
	int blk=32750;
	int x=0,y=blk-1;
	while(x<n){
        if(y>n) y=n;
        qw=cnt;
        while(cnt>0&&qw--){
            int l=x,r=y;
            pii px=funk(l);
            pii py=funk(r);
            if(px.S>py.F) break;
            int a=px.S,b=py.F;
            if(fnd(b).S-fnd(a).S-query(a,b)==0) break;
            while(l<=r){
                int m=(l+r)/2;
                pii ppp=funk(m);
                int a=ppp.F,b=ppp.S;
                if(a<l&&b>r) break;
                if(a>=l&&b<=r){
                    if(abs(a-m)<abs(b-m)){
                        m=a;
                    }
                    else{
                        m=b;
                    }
                }
                else if(a>=l){
                    m=a;
                }
                else{
                    m=b;
                }
                if(fnd(m).F+fnd(m).S<mx){
                    cnt--;
                    update(m+1,1);
                    if(fnd(m).F+fnd(m).S==0) return m;
                    p[m]=1;
                    break;
                }
                if(fnd(m).F-query(1,m)>0){
                    r=m-1;
                }
                else{
                    l=m+1;
                }
            }
        }
        x+=blk;
        y+=blk;
	}
	
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:121:1: warning: control reaches end of non-void function [-Wreturn-type]
  121 | }
      | ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1872 KB Output is correct
2 Correct 6 ms 1876 KB Output is correct
3 Correct 5 ms 1840 KB Output is correct
4 Incorrect 4 ms 1840 KB Integer 200000 violates the range [0, 199999]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1904 KB Output is correct
2 Correct 5 ms 1872 KB Output is correct
3 Correct 3 ms 1872 KB Output is correct
4 Incorrect 4 ms 1872 KB Integer 200000 violates the range [0, 199999]
5 Halted 0 ms 0 KB -