oj.uz

Submission #786191

# Submission time Handle Problem Language Result Execution time Memory
786191 2023-07-18T05:13:18 Z Khizri The Big Prize (IOI17_prize) C++17
20 / 100
 1000 ms 2304 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 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};
}
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]};
}
int find_best(int N) {
    n=N;
	memset(l,-1,sizeof(l));
	memset(r,-1,sizeof(r));
	int qq=450;
	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]);
	}
	for(int i=0;i<n;i++){
        if(l[i]!=-1&&l[i]+r[i]<mx){
            p[i]=1;
        }
	}
	int cnt=mx;
	int qw=cnt;
	int blk=500;
	int x=0,y=blk-1;
	while(x<n){
        if(y>=n) y=n-1;
        qw=cnt;
        while(cnt>0&&qw--){
            int l=x,r=y;
            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 if(fnd(m).S-fnd(funk(y).F).S-query(m+1,funk(y).F+1)>0){
                    l=m+1;
                }
                else{
                    break;
                }
            }
        }
        x+=blk;
        y+=blk;
	}

}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1848 KB Output is correct
2 Correct 5 ms 1964 KB Output is correct
3 Correct 8 ms 1872 KB Output is correct
4 Correct 11 ms 1872 KB Output is correct
5 Correct 8 ms 1856 KB Output is correct
6 Correct 4 ms 1872 KB Output is correct
7 Correct 9 ms 1856 KB Output is correct
8 Correct 4 ms 1904 KB Output is correct
9 Correct 6 ms 1844 KB Output is correct
10 Correct 6 ms 1884 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1876 KB Output is correct
2 Correct 9 ms 1876 KB Output is correct
3 Correct 4 ms 1876 KB Output is correct
4 Correct 11 ms 1856 KB Output is correct
5 Correct 8 ms 1876 KB Output is correct
6 Correct 2 ms 1904 KB Output is correct
7 Correct 9 ms 1864 KB Output is correct
8 Correct 8 ms 1872 KB Output is correct
9 Correct 8 ms 1872 KB Output is correct
10 Correct 9 ms 1872 KB Output is correct
11 Correct 7 ms 1968 KB Output is correct
12 Correct 4 ms 1864 KB Output is correct
13 Correct 7 ms 2304 KB Output is correct
14 Correct 4 ms 1872 KB Output is correct
15 Correct 8 ms 1996 KB Output is correct
16 Execution timed out 3013 ms 2140 KB Time limit exceeded
17 Halted 0 ms 0 KB -