제출 #146295

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146295		TadijaSebez	코알라 (APIO17_koala)	C++11	47 / 100	56 ms	884 KiB

koala

#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];
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 0 / 53