제출 #859257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
859257		abcvuitunggio	커다란 상품 (IOI17_prize)	C++17	100 / 100	36 ms	12812 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> a[200000];
int ch[200000],ch2[200000],st[800001],f[200001];
void build(int node, int l, int r){
    st[node]=r-l+1;
    if (l==r)
        return;
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
}
void update(int node, int l, int r, int i){
    if (l>i||r<i)
        return;
    if (l==r){
        st[node]=0;
        return;
    }
    int mid=(l+r)>>1;
    update(node<<1,l,mid,i);
    update(node<<1|1,mid+1,r,i);
    st[node]=st[node<<1]+st[node<<1|1];
}
int get(int node, int l, int r, int u, int v){
    if (l>v||r<u||l>r)
        return 0;
    if (l>=u&&r<=v)
        return st[node];
    int mid=(l+r)>>1;
    return get(node<<1,l,mid,u,v)+get(node<<1|1,mid+1,r,u,v);
}
int get(int node, int l, int r, int x){
    if (l==r)
        return l;
    int mid=(l+r)>>1;
    return (st[node<<1]>=x?get(node<<1,l,mid,x):get(node<<1|1,mid+1,r,x-st[node<<1]));
}
void query(int i){
    if (a[i].empty())
        a[i]=ask(i);
}
void update(int i){
    ch2[i]=1;
    i++;
    for (;i<=200000;i+=i&(-i))
        f[i]++;
}
int get(int i){
    i++;
    int res=0;
    for (;i;i-=i&(-i))
        res+=f[i];
    return res;
}
int b[4]={1,5,26,472};
int best(vector <int> v, int idx){
    memset(ch,0,sizeof(ch));
    memset(ch2,0,sizeof(ch2));
    memset(f,0,sizeof(f));
    if (v.size()==1)
        return v[0];
    if (v.size()<=b[idx]){
        for (int i=0;i<v.size();i++){
            query(v[i]);
            if (!a[v[i]][0]&&!a[v[i]][1])
                return v[i];
        }
    }
    int n=v.size(),mx=0;
    build(1,0,n-1);
    for (int i=0;i<b[idx];i++){
        query(v[i]);
        if (!a[v[i]][0]&&!a[v[i]][1])
            return v[i];
        mx=max(mx,a[v[i]][0]+a[v[i]][1]);
    }
    int cur=0;
    for (int i=0;i<b[idx];i++){
        update(1,0,n-1,i);
        if (a[v[i]][0]+a[v[i]][1]==mx){
            cur=i;
            break;
        }
        else
            update(i);
    }
    priority_queue <int, vector <int>, greater <int>> q;
    vector <int> v2;
    while (a[v[cur]][1]<n-cur-1){
        while (!q.empty()){
            if (a[v[q.top()]][0]==get(q.top())){
                cur=q.top();
              	q.pop();
            }
            else
                break;
        }
        vector <int> ve;
        int l=1,r=get(1,0,n-1,cur,(q.empty()?n-1:q.top()-1)),val=get(1,0,n-1,0,cur-1);
        if (!q.empty()&&q.top()-cur-1==a[v[q.top()]][0]-a[v[cur]][0]){
            for (int i=cur+1;i<q.top();i++){
                v2.push_back(v[i]);
                update(1,0,n-1,i);
                if (!ch2[i])
                    update(i);
            }
            continue;
        }
        while (l<=r){
            int mid=(l+r)>>1;
            int pos=get(1,0,n-1,val+mid);
            query(v[pos]);
            ve.push_back(pos);
            if (!a[v[pos]][0]&&!a[v[pos]][1])
                return v[pos];
            if (a[v[pos]][0]+a[v[pos]][1]==mx){
                if (a[v[pos]][0]>get(pos)){
                    if (!ch[pos])
                        q.push(pos);
                    ch[pos]=1;
                    r=mid-1;
                }
                else{
                    cur=pos;
                    break;
                }
                continue;
            }
            update(pos);
            v2.push_back(v[pos]);
            break;
        }
        for (int i:ve)
            update(1,0,n-1,i);
    }
    for (int i=cur+1;i<n;i++)
        v2.push_back(v[i]);
    sort(v2.begin(),v2.end());
    v2.resize(unique(v2.begin(),v2.end())-v2.begin());
    return best(v2,idx-1);
}
int find_best(int n){
    vector <int> v;
    for (int i=0;i<n;i++)
        v.push_back(i);
    return best(v,3);
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int best(std::vector<int>, int)':
prize.cpp:64:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     if (v.size()<=b[idx]){
      |         ~~~~~~~~^~~~~~~~
prize.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int i=0;i<v.size();i++){
      |                      ~^~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80