Submission #1041469

#TimeUsernameProblemLanguageResultExecution timeMemory
1041469Edu175Koala Game (APIO17_koala)C++17
57 / 100
61 ms600 KiB
#include "koala.h" #include <bits/stdc++.h> #define pb push_back #define fst first #define snd second #define fore(i,a,b) for(ll i=a,mxcont=b;i<mxcont;i++) #define SZ(x) ((int)x.size()) #define ALL(x) x.begin(),x.end() #define mset(a,v) memset((a),(v),sizeof(a)) #define imp(v) {for(auto jfhg:v)cout<<jfhg<<" ";cout<<"\n";} using namespace std; typedef int ll; typedef pair<ll,ll> ii; random_device rd; mt19937 rng(rd()); int minValue(int n, int w) { assert(w); int B[n],R[n]; fore(i,0,n)B[i]=R[i]=0; B[0]=1; playRound(B,R); ll mn=-1; fore(i,0,n)if(B[i]>=R[i])mn=i; return mn; } ll fn(ll n){return n*(n+1)/2;} ll n,w; vector<ll> alice(vector<ll>&b){ vector<vector<ll>>dp(n+1,vector<ll>(w+1)); for(ll i=n-1;i>=0;i--)fore(u,0,w+1){ ll &res=dp[i][u]; res=dp[i+1][u]; if(u+b[i]+1<=w)res=max(res,i+1+dp[i+1][u+b[i]+1]); } ll u=0; vector<ll>r(n); fore(i,0,n){ ll q=0; if(u+b[i]+1<=w&&dp[i][u]==i+1+dp[i+1][u+b[i]+1])q=b[i]+1; r[i]=q; u+=q; } return r; } ll old=-1,val=-1; void new_t(vector<ll>&t, vector<ll>B, vector<ll>R){ vector<vector<ll>>h(n,vector<ll>(2)); fore(i,0,n)h[t[i]][R[i]>B[i]]=1; ll cnt=0; fore(i,0,n)fore(j,0,2)if(h[i][j])h[i][j]=cnt++; fore(i,0,n)t[i]=h[t[i]][R[i]>B[i]]; } vector<ll>b,t,best; ll value(vector<ll>r){ auto t_=t; new_t(t_,b,r); return *max_element(ALL(t_)); } ll s; // map<vector<ll>,vector<ll>>dp; ll increasing=1; void f(){ // if(!SZ(b)&&dp.count(t)){best=dp[t];return;} if(SZ(b)==n){ ll vali=value(alice(b)); if(val==-1||vali>val)best=b,val=vali;//,dp[t]=best; // maximize value return; } ll i=SZ(b); auto go=[&](ll v){ if(val>old)return; s+=v; b.pb(v); if(s<=w)f(); s-=v; b.pop_back(); }; if(i&&t[i]==t[i-1])go(b.back()); else fore(v,increasing&&SZ(b)?b.back():0,w-s+1)go(v); } ll i=0,j=1; int greaterValue(int n, int w) { ll res=-1; auto qan=[&](ll x)->int{ // cout<<"qan "<<x<<"\n"; vector<ll>B(n),R(n); B[i]=B[j]=x; playRound(B.data(),R.data()); // imp(B); imp(R); vector<ll>s(n); fore(i,0,n)s[i]=R[i]>B[i]; // imp(s); if(s[i]!=s[j])res=s[i]<s[j]; return s[i]+s[j]; }; vector<vector<ll>>magic={{1, 2, 4, 8},{1, 2, 4, 7, 12}}; ll sub=w==200; ll l=0,r=SZ(magic[sub])-1; while(l<=r){ ll m=(l+r)/2; if(qan(magic[sub][m])==2)l=m+1; else r=m-1; } return res; } bool compare(ll i_, ll j_){ i=i_,j=j_; ll ret=greaterValue(n,w); // cout<<"compare "<<i<<" "<<j<<": "<<ret<<"\n"; return ret; } void msort(vector<ll>&a){ if(SZ(a)<=1)return; ll n=SZ(a),m=n/2; vector<ll>l,r; fore(i,0,m)l.pb(a[i]); fore(i,m,n)r.pb(a[i]); msort(l); msort(r); a.clear(); reverse(ALL(l)); reverse(ALL(r)); while(SZ(l)||SZ(r)){ ll ele=0; if(!SZ(l))ele=1; else if(!SZ(r))ele=0; else ele=!compare(l.back(),r.back()); if(ele)a.pb(r.back()),r.pop_back(); else a.pb(l.back()),l.pop_back(); } } vector<ll>ty; ll cnt=0; void strat(){ if(val==n)return; old=val; val=-1; if(cnt>=33){ vector<ll>ans; // cout<<"strat "<<cnt<<": "; imp(t); imp(ty); fore(v,0,50){ vector<ll>a; fore(i,0,n)if(ty[i]==v)a.pb(i); // cout<<"subarray "<<v<<": "; imp(a); msort(a); for(auto i:a)ans.pb(i); } fore(i,0,n)ty[ans[i]]=i; return; } f(); vector<ll>ks(n); fore(i,0,n)ks[t[i]]=best[i]; vector<ll>B(n),R(n); fore(i,0,n)B[i]=ks[ty[i]]; playRound(B.data(),R.data()); // for(auto i:b)cout<<i<<"" // imp(B); imp(R); new_t(ty,B,R); auto r=alice(best); new_t(t,best,r); // imp(best) imp(r); cout<<"\n"; cnt++; strat(); } int maxValue(int N, int W) { n=N,w=W; /*t=ty=vector<ll>(n); strat(); ll mx=0; fore(i,0,n)if(ty[i]>ty[mx])mx=i; return mx;*/ return 0; } void allValues(int N, int W, int *P) { n=N,w=W; t=ty=vector<ll>(n); old=1,val=-1; strat(); fore(i,0,n)P[i]=ty[i]+1; // if (W == 2*N) { // } else { // } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...