oj.uz

답안 #781996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
781996 2023-07-13T14:37:51 Z Khizri 커다란 상품 (IOI17_prize) C++17
0 / 100
 1000 ms 1908 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(p[l]==1) l--;
    while(p[r]==1) r++;
    return {l,r};
}
int find_best(int N) {
    n=N;
	if(n<=10000){
        for(int i = 0; i < n; i++) {
            std::vector<int> res = ask(i);
            if(res[0] + res[1] == 0)
                return i;
        }
	}
	memset(l,-1,sizeof(l));
	memset(r,-1,sizeof(r));
	int qq=500;
	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 qw=10;
	int cnt=mx;
	while(cnt>0&&qw--){
        int l=1,r=n;
        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);
                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;
            }
        }
	}
}

Compilation message

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

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1908 KB Output is correct
2 Correct 4 ms 1836 KB Output is correct
3 Correct 5 ms 1872 KB Output is correct
4 Correct 5 ms 1872 KB Output is correct
5 Correct 3 ms 1872 KB Output is correct
6 Execution timed out 3039 ms 1848 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1872 KB Output is correct
2 Correct 6 ms 1868 KB Output is correct
3 Correct 5 ms 1836 KB Output is correct
4 Correct 4 ms 1872 KB Output is correct
5 Correct 5 ms 1872 KB Output is correct
6 Execution timed out 3053 ms 1872 KB Time limit exceeded
7 Halted 0 ms 0 KB -