Submission #212670

#	Time	Username	Problem	Language	Result	Execution time	Memory
212670		zscoder	Koala Game (APIO17_koala)	C++17	100 / 100	338 ms	888 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> pbds;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

int minValue(int N, int W) {
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    int B[N];
    for(int i = 0; i < N; i++)
    {
		B[i]=0;
	}	
	B[0]=1;
    int R[N];
    playRound(B,R);
    for(int i = 0; i < N; i++)
    {
		if(R[i]<=B[i])
		{
			return i;
		}
	}
	return 0;
}


int findMax(vi &vec)
{
	int n = vec.size();
	//cerr<<n<<'\n';
	static int B[100];
	static int R[100];
	static bool good[100];
	if(n==1) return vec[0];
	for(int i = 0; i < 100; i++) 
	{
		good[i]=0;
		B[i]=0;
	}
	for(int i=0;i<vec.size();i++)
	{
		good[vec[i]]=1;
		B[vec[i]]=100/n;
	}
	playRound(B,R);
	vec.clear();
	for(int i=0;i<100;i++)
	{
		if(good[i]&&R[i]>B[i])
		{
			vec.pb(i);
		}
	}
	return findMax(vec);
}

int maxValue(int N, int W) {
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    vi v;
    for(int i=0;i<N;i++) v.pb(i);
    return findMax(v);
}

int testgreatervalue(int x)
{
	static int B[100];
	static int R[100];
	for(int i = 0; i < 100; i++) B[i] = 0;
	B[0]=B[1]=x;
	playRound(B,R);
	bool selecta = 0;
	bool selectb = 0;
	if(R[0]>B[0]) selecta=1;
	if(R[1]>B[1]) selectb=1;
	if(selecta^selectb)
	{
		if(selecta) return 0;
		else return 1;
	}
	else 
	{
		if(selecta) return -1;
		else return -2;
	}
}
int mm[6] = {1,2,4,6,7,8};
int greaterValue(int N, int W) {
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
	int lo = 0; int hi = 5;
	while(lo<=hi)
	{
		int mid = (lo+hi)>>1;
		int tmp = testgreatervalue(mm[mid]);
		if(tmp>=0) 
		{
			//ofstream fout("koalapre.txt");
			//cout<<mm[mid]<<",";
			return tmp;
		}
		if(tmp==-1)
		{
			lo=mid+1;
		}
		else
		{
			hi=mid-1;
		}
	}
	//cout<<"ERROR\n";
    return 0;
}

ii dp[101][101];
int moves[101][101];
typedef long double ld;
const int NN = 100;
int test(int x, int p1, int p2)
{
	static int B[100];
	static int R[100];
	for(int i = 0; i < 100; i++) B[i] = 0;
	B[p1]=B[p2]=x;
	playRound(B,R);
	bool selecta = 0;
	bool selectb = 0;
	if(R[p1]>B[p1]) selecta=1;
	if(R[p2]>B[p2]) selectb=1;
	if(selecta^selectb)
	{
		if(selecta) return 0;
		else return 1;
	}
	else 
	{
		if(selecta) return -1;
		else return -2;
	}
}
int greedydp(int l, int r, int a, int b) //a from [1, l - 1], b from [l, r]
{
	vector<pair<ld,int> > vec;
	for(int i = 1; i < l; i++)
	{
		vec.pb(mp(ld(i)/ld(a),i));
	}
	for(int i = l; i <= r; i++)
	{
		vec.pb(mp(ld(i)/ld(b),i));
	}
	sort(vec.rbegin(),vec.rend());
	int sum=0;
	int cnt = r;
	for(int i=0;i<r;i++)
	{
		if(vec[i].se>=l)
		{
			if(sum+b<=r)
			{
				cnt--;
				sum+=b;
			}
			else
			{
				continue;
			}
		}
		else
		{
			if(sum+a<=r)
			{
				sum+=a;
			}
			else continue;
		}
	}
	return cnt;
}

int realdp(int l, int r, int a, int b)
{
	//cerr<<l<<' '<<r<<' '<<a<<' '<<b<<'\n';
	pair<int,int> dp2[r+1][r+1];
	for(int i = 0; i <= r; i++)
	{
		for(int j= 0;j<=r;j++)
		{
			dp2[i][j]=mp(-1,-1);
		}
	}
	dp2[1][0] = mp(0,0);
	if(a<=r) 
	{
		if(l==0) dp2[1][a] = mp(1,1);
		else dp2[1][a] = mp(1,0);
	}
	for(int i = 2; i <= r; i++)
	{
		for(int j = 0; j <= r; j++)
		{
			dp2[i][j] = dp2[i-1][j];
			int cost = a;
			if(i>=l) cost=b;
			if(j>=cost)
			{
				int cc=0;
				if(i>=l) cc++;
				dp2[i][j] = max(dp2[i][j],mp(dp2[i-1][j-cost].fi+i,dp2[i-1][j-cost].se+cc));
			}
		}
	}
	ii best=mp(-1,-1);
	for(int i = 0; i <= r; i++)
	{
		best=max(best,dp2[r][i]);
	}
	//cerr<<l<<' '<<r<<' '<<a<<' '<<b<<'\n';
	return r-best.se;
}

const int C1 = 20;
const int C2 = 30;
int solve(int l, int r)
{
	//
	if(moves[l][r]!=-1) return moves[l][r];
	if(l>r) return 0;
	if(l==r)
	{
		return (moves[l][r]=0);
	}
	if(r-l>=2)
	{
		//cerr<<"SOLVE : "<<l<<' '<<r<<'\n';
		int cc=0;
		ii best = mp(-1,-1);
		int bestres = 100000;
		for(int a = 1; a < C1; a++)
		{
			for(int b = a + 1; b < C2; b++)
			{
				if((a-1)*l+(b-1)*(r-l)>NN) continue;
				int mid = 0;
				if(r-l>8) mid = greedydp(l,r,a,b);
				else mid = realdp(l,r,a,b);
				//if(l==1&&r==10) cerr<<l<<' '<<r<<' '<<a<<' '<<b<<' '<<mid<<'\n';
				if(mid+1==l||r==mid) continue;
				int mov = 1 + solve(l,mid) + solve(mid+1,r);
				if(mov<bestres)
				{
					bestres=mov;
					best=mp(a,b);
					cc++;
				}
				if(cc>=3) break;
			}
			if(cc>=3) break;
		}
		if(bestres==100000) assert(0);
		dp[l][r] = best;
		return (moves[l][r] = bestres);
	}
	else
	{
		return (moves[l][r]=1);
	}
}

int ans[101];
bool mode2;
const int MAGIC1[100] = {1,1,1,2,2,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8};
const int MAGIC2[100] = {1,1,1,2,2,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8};
void play(int l, int r, vi vec, vi L)
{
	//cerr<<l<<' '<<r<<'\n';
	if(l==r) 
	{
		ans[vec[0]] = l;
		return ;
	}
	if(r-l<2)
	{
		
		int mid = MAGIC1[l-1];
		int tmp = test(mid,vec[0],vec[1]);
		if(tmp>=0) 
		{
			if(tmp==0)
			{
				ans[vec[0]] = l+1;
				ans[vec[1]] = l;
			}
			else
			{
				ans[vec[0]]=l;
				ans[vec[1]]=l+1;
			}
			return ;
		}
		assert(tmp>=0);
		
		/*
		int lo = 0; int hi = 5;
		while(lo<=hi)
		{
			int mid = (lo+hi)>>1;
			int tmp = test(mm[mid],vec[0],vec[1]);
			if(tmp>=0) 
			{
				//ofstream fout("koalapre.txt");
				//cout<<mid<<",";
				if(tmp==0)
				{
					ans[vec[0]] = l+1;
					ans[vec[1]] = l;
				}
				else
				{
					ans[vec[0]]=l;
					ans[vec[1]]=l+1;
				}
				return ;
			}
			if(tmp==-1)
			{
				lo=mid+1;
			}
			else
			{
				hi=mid-1;
			}
		}
		*/
	}
	if(l>r) return ;
	if(moves[l][r]==-1) solve(l,r);
	ii mov = dp[l][r];
	//cerr<<"HERE\n";
	static int B[100];
	static int R[100];
	assert(L.size()==l-1);
	assert(vec.size()==r-l+1);
	//cerr<<l<<' '<<r<<' '<<mov.fi<<' '<<mov.se<<'\n';
	for(int i = 0; i < NN; i++)
	{
		B[i]=0;
	}
	for(int i = 0; i < L.size(); i++) 
	{
		B[L[i]]=mov.fi-1;
	}
	for(int i = 0; i < vec.size(); i++) 
	{
		B[vec[i]]=mov.se-1;
	}
	playRound(B,R);
	vi le,ri;
	vi Ltmp = L;
	int mid = r+1;
	//cerr<<"HERE\n";
	for(int i = 0; i < vec.size(); i++)
	{
		if(R[vec[i]]>B[vec[i]])
		{
			ri.pb(vec[i]);
			mid--;
		}
		else
		{
			le.pb(vec[i]);
		}
	}
	//cerr<<l<<' '<<mid<<' '<<r<<' '<<mov.fi<<' '<<mov.se<<'\n';
	for(int i=0;i<le.size();i++) Ltmp.pb(le[i]);
	play(l,mid-1,le,L);
	play(mid,r,ri,Ltmp);
}

int queries=0;
bool cmp(int x, int y)
{
	queries++;
	assert(queries<=700);
	static int B[100];
	static int R[100];
	for(int i=0;i<100;i++) B[i]=0;
	B[x]=100; B[y]=100;
	playRound(B,R);
	if(R[x]>B[x]) return false; //value at x is higher
	return true;
}

void allValues(int N, int W, int *P) {
	memset(moves,-1,sizeof(moves));
    if (W == 2*N) 
    {
		for(int i=0;i<N;i++) P[i]=i;
		stable_sort(P,P+N,cmp);
		vi Q(N);
		for(int i=0;i<N;i++) Q[P[i]]=i+1;
		for(int i=0;i<N;i++) P[i]=Q[i];
        // 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.
        vi v,w;
        mode2=0;
        for(int i=0;i<N;i++) v.pb(i);
        play(1,N,v,w);
        for(int i=0;i<N;i++)
        {
			P[i]=ans[i];
		}
    }
}

Compilation message (stderr)

koala.cpp: In function 'int findMax(vi&)':
koala.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec.size();i++)
              ~^~~~~~~~~~~
In file included from /usr/include/c++/7/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45:0,
                 from /usr/include/c++/7/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/7/ext/pb_ds/assoc_container.hpp:48,
                 from koala.cpp:3:
koala.cpp: In function 'void play(int, int, vi, vi)':
koala.cpp:359:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(L.size()==l-1);
         ~~~~~~~~^~~~~
koala.cpp:360:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(vec.size()==r-l+1);
         ~~~~~~~~~~^~~~~~~
koala.cpp:366:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < L.size(); i++) 
                 ~~^~~~~~~~~~
koala.cpp:370:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vec.size(); i++) 
                 ~~^~~~~~~~~~~~
koala.cpp:379:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vec.size(); i++)
                 ~~^~~~~~~~~~~~
koala.cpp:392:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<le.size();i++) Ltmp.pb(le[i]);
              ~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 53 / 53