Submission #1134607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134607		t9unkubj	The Big Prize (IOI17_prize)	C++20	20 / 100	28 ms	2224 KiB

prize

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#include"prize.h"
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
int find_best(int n);
namespace judge{
    
static const int max_q = 10000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;

    vector<int> ask(int i) {
	    query_count++;
	    if(query_count > max_q) {
		    cerr << "Query limit exceeded" << endl;
		    exit(0);
	    }

	    if(i < 0 || i >= n) {
		    cerr << "Bad index: " << i << endl;
		    exit(0);
	    }

	    vector<int> res(2);
	    res[0] = rank_count[g[i] - 1][i + 1];
	    res[1] = rank_count[g[i] - 1][n] - res[0];
	    return res;
    }

    void run(int n_,vc<int>a){
        n=n_;
        g=a;
	    int max_rank = *max_element(g.begin(), g.end());

	    rank_count.resize(max_rank + 1, vector<int>(n + 1, 0));
	    for(int r = 0; r <= max_rank; r++) {
		    for(int i = 1; i <= n; i++) {
			    rank_count[r][i] = rank_count[r][i - 1];
			    if(g[i - 1] == r)
			        rank_count[r][i]++;
		    }
	    }

	    for(int i = 0; i <= n; i++)
		    for(int r = 1; r <= max_rank; r++)
			    rank_count[r][i] += rank_count[r - 1][i];

	    assert(a[find_best(n)]==1);
	    cout << "Query count: " << query_count << endl;

	    return ;
    }
};

#ifdef t9unkubj
using namespace judge;
#endif
/*
二分探索
"上"の階層のものがわかるので頑張る
*/
vc<int> Ask(int x){
    static map<int,vc<int>>memo;
    if(memo.count(x))return memo[x];
    return memo[x]=ask(x);
}
int find_best(int n) {
    vc<int>is;
    rep(i,n)is.push_back(i);

    int low_cnt=0;
    constexpr int B=448;
    rep(i,min(B,n)){
        chmax(low_cnt,Ask(i)[0]+Ask(i)[1]);
    }
   
    {
        vc<int>nxt_is;
        set<pair<int,int>>le,ri;
        queue<pair<int,int>>now_que,nxt_que;
        vc<array<int,3>>update;
        int mid=is.size()>>1;
        auto res=Ask(is[mid]);
        le.insert({mid,res[0]});
        ri.insert({mid,res[1]});
        now_que.push({0,is.size()});
        while(1){
            if(now_que.size()){
                auto [l,r]=now_que.front();now_que.pop();
                
                if(l==r)continue;
                if(l+1==r){
                    if(Ask(is[l])[0]+Ask(is[l])[1]<low_cnt)
                        nxt_is.push_back(is[l]);
                    continue;
                }
                int mid=l+r>>1;
                auto res=Ask(is[mid]);

                int r0=res[0],r1=res[1];
                {
                    auto it=le.lower_bound({is[mid],-1});
                    if(it!=le.begin())r0-=prev(it)->second;
                }
                {
                    auto it=ri.lower_bound({is[mid]+1,-1});
                    if(it!=ri.end())r1-=it->second;
                }
                if(res[0]+res[1]<low_cnt){
                    nxt_is.push_back(is[mid]);
                }

                if(res[0]+res[1]<low_cnt||r0){
                    if(mid-l>1){
                        int nxt_mid=mid+l>>1;
                        auto R=Ask(is[nxt_mid]);
                        if(R[0]+R[1]==low_cnt)
                            update.push_back({nxt_mid,R[0],R[1]});
                    }
                    nxt_que.push({l,mid});
                }
                if(res[0]+res[1]<low_cnt||r1){
                    if(r-(mid+1)>1){
                        int nxt_mid=(mid+1+r)>>1;
                        auto R=Ask(is[nxt_mid]);
                        if(R[0]+R[1]==low_cnt)
                            update.push_back({nxt_mid,R[0],R[1]});
                    }
                    nxt_que.push({mid+1,r});
                }
            }else if(nxt_que.size()){
                now_que=move(nxt_que);
                for(auto&[x,y,z]:update)
                    le.insert({x,y}),ri.insert({x,z});
                update.clear();
            }else break;
        }
        pair<int,int>ans{1e9,1e9};
        for(auto&i:nxt_is){
            chmin(ans,pair<int,int>{Ask(i)[0]+Ask(i)[1],i});
        }
        return ans.second;
    }
}
vc<int>make(int n){
    vc<int>ap{1};
    while(1){
        ll r=ap.back();
        if(r*r+1+accumulate(all(ap),0)>n){
            ap.back()+=n-accumulate(all(ap),0);
            vc<int>is;
            rep(i,ap.size())rep(j,ap[i])is.push_back(i+1);
            return is;
        }
        ap.push_back(r*r+1);
    }
    std::chrono::steady_clock().now().time_since_epoch().count();
}
#ifdef t9unkubj
void run1(){
    mt19937 mt(4);
    int n=2e5;
    auto a=make(n);
    shuffle(all(a),mt);
    dbg(a.size());
    run(n,a);
    dbg("OKOK"s);
}
void run2(){
    int n;
    cin>>n;
    vc<int>a(n);
    rep(i,n)cin>>a[i];
    run(n,a);
}
int main(){while(1)run1();}
#endif
/*
8
3 2 3 1 3 3 2 3

*/

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