Submission #981331

#	Time	Username	Problem	Language	Result	Execution time	Memory
981331		pcc	Koala Game (APIO17_koala)	C++17	66 / 100	41 ms	852 KiB

koala

#include "koala.h"

#include <bits/stdc++.h>

using namespace std;
const int mxn = 110;

int ask[mxn],res[mxn];
int N,W;

void play(int* a,int* b){
	//cerr<<"ASK:"<<endl;for(int i = 0;i<N;i++)cerr<<a[i]<<(i%10 == 9?"\n":" ");cerr<<endl;
	playRound(a,b);
	//cerr<<"RES:"<<endl;for(int i = 0;i<N;i++)cerr<<b[i]<<(i%10 == 9?"\n":" ");cerr<<endl;
}

namespace S1{
	int GO(){
		memset(ask,0,sizeof(ask));
		ask[0] = 1;
		play(ask,res);
		 if(res[0] == 2){
			for(int i = 1;i<N;i++)if(!res[i])return i;
			assert(false);
		}
		else return 0;
		memset(ask,0,sizeof(ask));
		ask[1] = 1;
		play(ask,res);
		for(int i = 2;i<N;i++)if(!res[i])return i;
		assert(false);
		return -1;
	}
}

int minValue(int NN, int WW) {
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
	N = NN,W = WW;
	return S1::GO();
}

namespace S2{
	int GO(){
		for(int i = 0;i<N;i++)ask[i] = 1;
		play(ask,res);
		int num = N/2;
		while(num>1){
			int cnt = 0;
			for(int i = 0;i<N;i++)if(res[i]==1)res[i] = 0;
			int val = N/num;
			for(int i = 0;i<N;i++){
				if(res[i])res[i] = val;
			}
			play(res,res);
			num = 0;
			for(int i = 0;i<N;i++){
				num += res[i]>1;
			}
		}
		for(int i = 0;i<N;i++)if(res[i]>=*max_element(res,res+N))return i;
		assert(false);
	}
}

int maxValue(int NN, int WW) {
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
	N = NN,W = WW;
	return S2::GO();
}

namespace S3{
	int GO(){

		int l = 1,r = 12;
		while(l != r){
			int mid = (l+r)>>1;
			memset(ask,0,sizeof(ask));
			ask[0] = ask[1] = mid;
			play(ask,res);
			if(res[0]>mid&&res[1]>mid)l = mid+1;
			else if(res[0]<=mid&&res[1]<=mid)r = mid-1;
			else if(res[0]>mid)return 0;
			else if(res[1]>mid)return 1;
		}
		ask[0] = ask[1] = l;
		play(ask,res);
		return (res[0]>l?0:1);

	}
}

int greaterValue(int NN, int WW) {
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
	N = NN,W = WW;
	return S3::GO();
}


namespace S5{
	int dp[mxn][mxn];

	bool cmp(int a,int b){
		if(dp[a][b] != -1)return dp[a][b];
		int l = 1,r = 12;
		while(l != r){
			int mid = (l+r)>>1;
			memset(ask,0,sizeof(ask));
			ask[a] = ask[b] = mid;
			play(ask,res);
			if(res[a]>mid&&res[b]>mid)l = mid+1;
			else if(res[a]<=mid&&res[b]<=mid)r = mid-1;
			else if(res[a]>mid)return 0;
			else if(res[b]>mid)return 1;
		}
		memset(ask,0,sizeof(ask));
		ask[a] = ask[b] = l;
		play(ask,res);
		return dp[a][b] = (res[a]>l?0:1);
	}

	int arr[mxn];
	void dc(int l,int r){
		if(l == r)return;
		int mid = (l+r)>>1;
		dc(l,mid);
		dc(mid+1,r);
		vector<int> lv,rv;
		for(int i = l;i<=mid;i++)lv.push_back(arr[i]);
		for(int i = mid+1;i<=r;i++)rv.push_back(arr[i]);
		reverse(lv.begin(),lv.end());
		reverse(rv.begin(),rv.end());
		int pt = l;
		while(!lv.empty()&&!rv.empty()){
			if(!cmp(lv.back(),rv.back())){
				arr[pt++] = rv.back();
				rv.pop_back();
			}
			else{
				arr[pt++] = lv.back();
				lv.pop_back();
			}
		}
		while(!lv.empty()){
			arr[pt++] = lv.back();
			lv.pop_back();
		}
		while(!rv.empty()){
			arr[pt++] = rv.back();
			rv.pop_back();
		}
		return;
	}
	void GO(int * P){
		memset(dp,-1,sizeof(dp));
		cerr<<"HI"<<endl;
		for(int i = 0;i<N;i++)arr[i] = i;
		srand(time(NULL));
		random_shuffle(arr,arr+N);
		dc(0,N-1);
		for(int i = 0;i<N;i++)cerr<<arr[i]<<' ';cerr<<endl;
		for(int i = 0;i<N;i++)P[arr[i]] = i+1;
		return;
	}
}

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

Compilation message (stderr)

koala.cpp: In function 'int S2::GO()':
koala.cpp:50:8: warning: unused variable 'cnt' [-Wunused-variable]
   50 |    int cnt = 0;
      |        ^~~
koala.cpp: In function 'bool S5::cmp(int, int)':
koala.cpp:124:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  124 |   return dp[a][b] = (res[a]>l?0:1);
      |          ~~~~~~~~~^~~~~~~~~~~~~~~~
koala.cpp: In function 'void S5::GO(int*)':
koala.cpp:166:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  166 |   for(int i = 0;i<N;i++)cerr<<arr[i]<<' ';cerr<<endl;
      |   ^~~
koala.cpp:166:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  166 |   for(int i = 0;i<N;i++)cerr<<arr[i]<<' ';cerr<<endl;
      |                                           ^~~~

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