oj.uz

Submission #146295

# Submission time Handle Problem Language Result Execution time Memory
146295 2019-08-23T10:25:18 Z TadijaSebez Koala Game (APIO17_koala) C++11
47 / 100
 56 ms 884 KB 
#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=105;
int A[N],B[N];
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.
	A[0]=1;
	for(int i=1;i<N;i++) A[i]=0;
	playRound(A,B);
	for(int i=0;i<N;i++) if(A[i]>=B[i]) return i;
	return -1;
}

void Clear(int N, int val=0){ for(int i=0;i<N;i++) A[i]=val;}
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.
	vector<int> cand(N);
	for(int i=0;i<N;i++) cand[i]=i;
	while(cand.size()>1)
	{
		Clear(N);
		int mx=0;while((mx+1)*(mx+2)/2<N) mx++;
		int put=min(W/(int)cand.size(),mx-1);
		for(int i:cand) A[i]=put;
		playRound(A,B);
		cand.clear();
		for(int i=0;i<N;i++) if(A[i]>0 && B[i]>A[i]) cand.push_back(i);
	}
	return cand[0];
}

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 top=0,bot=1,mid;
	while((top+1)*(top+2)/2<N) top++;
	while(top>=bot)
	{
		mid=top+bot>>1;
		Clear(N);
		A[0]=A[1]=mid;
		playRound(A,B);
		if(B[0]>A[0] && B[1]>A[1]) bot=mid+1;
		else if(B[0]<=A[0] && B[1]<=A[1]) top=mid-1;
		else break;
	}
	if(A[0]<B[0]) return 0;
	else return 1;
}
bool comp(int x, int y, int N, int W)
{
	Clear(N);
	A[x]=A[y]=W/2;
	playRound(A,B);
	if(A[x]<B[x]) return 0;
	if(A[y]<B[y]) return 1;
}
bool comp2(int x, int y, int N, int W)
{
	int top=0,bot=1,mid;
	while((top+1)*(top+2)/2<N) top++;
	while(top>=bot)
	{
		mid=top+bot>>1;
		Clear(N);
		A[x]=A[y]=mid;
		playRound(A,B);
		if(B[x]>A[x] && B[y]>A[y]) bot=mid+1;
		else if(B[x]<=A[x] && B[y]<=A[y]) top=mid-1;
		else break;
	}
	if(A[x]<B[x]) return 0;
	else return 1;
}
int C[N],D[N];
void MergeSort(int l, int r, function<bool(int,int)> cmp)
{
	if(l==r) return;
	int mid=l+r>>1;
	MergeSort(l,mid,cmp);
	MergeSort(mid+1,r,cmp);
	int i=l,j=mid+1,k=l;
	while(i<=mid || j<=r)
	{
		if(i>mid) D[k++]=C[j++];
		else if(j>r) D[k++]=C[i++];
		else if(cmp(C[i],C[j])) D[k++]=C[i++];
		else D[k++]=C[j++];
	}
	for(i=l;i<=r;i++) C[i]=D[i];
}
int ans[N];
int dp[N][N];
bool go[N][N],take[N];
const int inf=1e9+7;
int Simulate(int l, int r, int n, int w)
{
	int sum=(r-l+1)*w;
	for(int i=0;i<=n;i++) for(int j=0;j<=sum;j++) dp[i][j]=-inf;
	dp[0][0]=0;
	for(int i=1;i<=n;i++) for(int j=0;j<=sum;j++)
	{
		int need=1;
		if(l<=i && i<=r) need=w+1;
		go[i][j]=0;
		dp[i][j]=dp[i-1][j];
		if(j>=need && dp[i][j]<dp[i-1][j-need]+i)
		{
			go[i][j]=1;
			dp[i][j]=dp[i-1][j-need]+i;
		}
	}
	int ans=0;
	for(int j=1;j<=sum;j++) if(dp[n][j]>dp[n][ans]) ans=j;
	for(int i=n;i>=1;i--)
	{
		int need=1;
		if(l<=i && i<=r) need=w+1;
		take[i]=go[i][ans];
		if(take[i]) ans-=need;
	}
	int cnt[2]={0,0};
	for(int i=l;i<=r;i++) cnt[take[i]]++;
	return abs(cnt[0]-cnt[1]);
}
void Solve(int n, int W, int l, int r, vector<int> p)
{
	assert(p.size());
	if(l==r){ ans[p[0]]=l;return;}
	int sz=r-l+1,w=0,best=r-l+1;
	for(int i=1;i*sz<=W;i++)
	{
		int tmp=Simulate(l,r,n,i);
		if(tmp<best) w=i,best=tmp;
	}
	assert(w);
	Clear(N);
	for(int i:p) A[i]=w;
    playRound(A,B);
    vector<int> L,R;
    for(int i:p)
	{
		if(B[i]>A[i]) R.pb(i);
		else L.pb(i);
	}
	Solve(n,W,l,l+L.size()-1,L);
	Solve(n,W,l+L.size(),r,R);
}
void allValues(int N, int W, int *P) {
	if (W == 2*N) {
		// TODO: Implement Subtask 4 solution here.
		// You may leave this block unmodified if you are not attempting this
		// subtask.
		for(int i=0;i<N;i++) C[i]=i;
		MergeSort(0,N-1,[&](int x, int y){ return comp(x,y,N,W);});
		for(int i=0;i<N;i++) P[C[i]]=i+1;
	} else {
		// TODO: Implement Subtask 5 solution here.
		// You may leave this block unmodified if you are not attempting this
		// subtask.
		vector<int> v;
		for(int i=0;i<N;i++) v.pb(i);
		Solve(N,W,1,N,v);
		for(int i=0;i<N;i++) P[i]=ans[i];
	}
}

Compilation message

koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:46:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
koala.cpp: In function 'bool comp2(int, int, int, int)':
koala.cpp:71:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
koala.cpp: In function 'void MergeSort(int, int, std::function<bool(int, int)>)':
koala.cpp:86:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
koala.cpp: In function 'bool comp(int, int, int, int)':
koala.cpp:64:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 7 ms 380 KB Output is correct
4 Correct 7 ms 376 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 764 KB Output is correct
2 Correct 56 ms 732 KB Output is correct
3 Correct 51 ms 640 KB Output is correct
4 Correct 51 ms 748 KB Output is correct
5 Correct 52 ms 884 KB Output is correct
6 Correct 52 ms 732 KB Output is correct
7 Correct 54 ms 760 KB Output is correct
8 Correct 52 ms 760 KB Output is correct
9 Correct 51 ms 760 KB Output is correct
10 Correct 51 ms 860 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 376 KB Output is correct
2 Correct 36 ms 392 KB Output is correct
3 Correct 34 ms 380 KB Output is correct
4 Correct 34 ms 376 KB Output is correct
5 Correct 33 ms 376 KB Output is correct
6 Correct 34 ms 384 KB Output is correct
7 Correct 33 ms 424 KB Output is correct
8 Correct 33 ms 376 KB Output is correct
9 Correct 33 ms 376 KB Output is correct
10 Correct 32 ms 480 KB Output is correct
11 Correct 33 ms 376 KB Output is correct
12 Correct 21 ms 376 KB Output is correct
13 Correct 34 ms 376 KB Output is correct
14 Correct 32 ms 376 KB Output is correct
15 Correct 30 ms 376 KB Output is correct
16 Correct 29 ms 376 KB Output is correct
17 Correct 29 ms 396 KB Output is correct
18 Correct 31 ms 376 KB Output is correct
19 Correct 30 ms 376 KB Output is correct
20 Correct 30 ms 388 KB Output is correct

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -