oj.uz

Submission #212670

# Submission time Handle Problem Language Result Execution time Memory
212670 2020-03-24T04:23:33 Z zscoder Koala Game (APIO17_koala) C++17
100 / 100
 338 ms 888 KB 
#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

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.0 / 4.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 384 KB Output is correct
2 Correct 21 ms 384 KB Output is correct
3 Correct 22 ms 400 KB Output is correct
4 Correct 21 ms 384 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 384 KB Output is correct
2 Correct 93 ms 408 KB Output is correct
3 Correct 87 ms 432 KB Output is correct
4 Correct 82 ms 384 KB Output is correct
5 Correct 85 ms 384 KB Output is correct
6 Correct 92 ms 640 KB Output is correct
7 Correct 87 ms 384 KB Output is correct
8 Correct 83 ms 384 KB Output is correct
9 Correct 83 ms 384 KB Output is correct
10 Correct 83 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 504 KB Output is correct
2 Correct 53 ms 384 KB Output is correct
3 Correct 52 ms 384 KB Output is correct
4 Correct 51 ms 384 KB Output is correct
5 Correct 51 ms 384 KB Output is correct
6 Correct 52 ms 384 KB Output is correct
7 Correct 52 ms 384 KB Output is correct
8 Correct 52 ms 384 KB Output is correct
9 Correct 51 ms 432 KB Output is correct
10 Correct 50 ms 384 KB Output is correct
11 Correct 53 ms 384 KB Output is correct
12 Correct 25 ms 384 KB Output is correct
13 Correct 50 ms 384 KB Output is correct
14 Correct 47 ms 504 KB Output is correct
15 Correct 46 ms 384 KB Output is correct
16 Correct 48 ms 384 KB Output is correct
17 Correct 47 ms 384 KB Output is correct
18 Correct 47 ms 384 KB Output is correct
19 Correct 48 ms 428 KB Output is correct
20 Correct 48 ms 384 KB Output is correct

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 716 KB Output is correct
2 Correct 326 ms 572 KB Output is correct
3 Correct 329 ms 632 KB Output is correct
4 Correct 311 ms 504 KB Output is correct
5 Correct 334 ms 632 KB Output is correct
6 Correct 308 ms 504 KB Output is correct
7 Correct 314 ms 504 KB Output is correct
8 Correct 315 ms 504 KB Output is correct
9 Correct 308 ms 504 KB Output is correct
10 Correct 330 ms 888 KB Output is correct
11 Correct 328 ms 504 KB Output is correct
12 Correct 334 ms 504 KB Output is correct
13 Correct 325 ms 572 KB Output is correct
14 Correct 324 ms 504 KB Output is correct
15 Correct 315 ms 572 KB Output is correct
16 Correct 316 ms 504 KB Output is correct
17 Correct 316 ms 732 KB Output is correct
18 Correct 304 ms 504 KB Output is correct
19 Correct 322 ms 632 KB Output is correct
20 Correct 310 ms 504 KB Output is correct
21 Correct 321 ms 504 KB Output is correct
22 Correct 321 ms 480 KB Output is correct
23 Correct 321 ms 504 KB Output is correct
24 Correct 319 ms 760 KB Output is correct
25 Correct 303 ms 504 KB Output is correct
26 Correct 326 ms 504 KB Output is correct
27 Correct 323 ms 504 KB Output is correct
28 Correct 324 ms 504 KB Output is correct
29 Correct 330 ms 504 KB Output is correct
30 Correct 323 ms 632 KB Output is correct
31 Correct 329 ms 632 KB Output is correct
32 Correct 320 ms 504 KB Output is correct
33 Correct 332 ms 636 KB Output is correct
34 Correct 323 ms 504 KB Output is correct
35 Correct 338 ms 504 KB Output is correct
36 Correct 303 ms 504 KB Output is correct
37 Correct 328 ms 504 KB Output is correct
38 Correct 328 ms 504 KB Output is correct
39 Correct 325 ms 520 KB Output is correct
40 Correct 327 ms 580 KB Output is correct