oj.uz

Submission #1041252

# Submission time Handle Problem Language Result Execution time Memory
1041252 2024-08-01T19:48:38 Z Edu175 Koala Game (APIO17_koala) C++17
9 / 100
 378 ms 600 KB 
#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 val=-1,cur;
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]];
}
void cap(vector<ll>&t){
    fore(i,0,n){
        if(t[i]<cur)t[i]=0;
        else if(t[i]==cur)t[i]=1;
        else t[i]=2;
    }
}
vector<ll>b,t,best;
ll value(vector<ll>r){
	ll c=0,sz=0;
	fore(i,0,n){
        if(t[i]==cur){
            c+=r[i]>b[i];
            sz++;
        }
	}
    return abs(c-sz/2);
}
ll s;
map<vector<ll>,vector<ll>>dp;
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; // minimize value
		return;
	}
	ll i=SZ(b);
	auto go=[&](ll v){
		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,0,w-s+1)go(v);
}
vector<ll>ty;
// ll cnt=0;
void strat(){
	if(ty[0]!=ty[1])return;
    // cout<<"strat\n"; imp(t); imp(ty);
	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());
    new_t(ty,B,R);
	auto r=alice(best);
    new_t(t,best,r);
	val=-1;
    cur=ty[0];
    cap(ty);
    cap(t);
    cur=ty[0];
    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;
}

int greaterValue(int N, int W) {
    n=N,w=W;
    t=ty=vector<ll>(n);
    cur=0;
    strat();
    return ty[0]<ty[1];
}

void allValues(int N, int W, int *P) {
    assert(P[0]);
    if (W == 2*N) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
5.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 160 ms 540 KB Output is partially correct
2 Partially correct 378 ms 592 KB Output is partially correct
3 Partially correct 120 ms 532 KB Output is partially correct
4 Partially correct 157 ms 344 KB Output is partially correct
5 Partially correct 155 ms 560 KB Output is partially correct
6 Partially correct 198 ms 540 KB Output is partially correct
7 Partially correct 180 ms 600 KB Output is partially correct
8 Partially correct 197 ms 520 KB Output is partially correct
9 Partially correct 164 ms 344 KB Output is partially correct
10 Partially correct 169 ms 520 KB Output is partially correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -