Submission #718770

#	Time	Username	Problem	Language	Result	Execution time	Memory
718770		pragmatist	Koala Game (APIO17_koala)	C++17	47 / 100	55 ms	440 KiB

koala

#include "koala.h"        
#include <bits/stdc++.h>

#define sz(v) (int)v.size()
#define pb push_back

using namespace std;      

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 n = N;
    int a[n], b[n];
    memset(a, 0, sizeof(a));
    a[0] = 1;
    playRound(a, b);    
    for(int i = 0; i < n; ++i) {
    	if(b[i] == 0) {
    		return i;
    	}
    }
    return 0;
}

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.
    int n = N, a[n], b[n];
   	vector<int> v;
   	for(int i = 0; i < n; ++i) {
   		v.pb(i);
   	}
   	while(sz(v) > 1) {
		int t = W / sz(v);
		bool used[n];
		memset(used, 0, sizeof(used));
		for(auto x : v) used[x] = 1;
		for(int i = 0; i < n; ++i) {
			if(!used[i]) {
				a[i] = 0;
			} else {
				a[i] = t;
			}
		}
		playRound(a, b);
		vector<int> to;
		for(int i = 0; i < n; ++i) {
			if(b[i] > t) {
				to.pb(i);
			}
		}
		v = to;		   		
   	}
    return v[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 n = N, a[n], b[n];
	int l = 1, r = min(9, W / 2), ans = -1;
	while(l <= r) {
		int mid = (l + r) >> 1;
		memset(a, 0, sizeof(a));	
		a[0] = a[1] = mid;
		playRound(a, b);   
		if(a[0] >= b[0] && a[1] >= b[1]) {
			r = mid - 1;
			continue;
		}
		bool c = (a[0] < b[0]), d = (a[1] < b[1]);
		if(c && d) {
			l = mid + 1;  
			continue;
		}
		ans = (c < d);
		break;
	}
	assert(ans != -1);
	return ans;
}

bool comp(int i, int j, int n) {
	int a[n], b[n];
	memset(a, 0, sizeof(a));
	a[i] = a[j] = n;
	playRound(a, b);
	assert((b[i] > a[i]) || (b[j] > a[j]));
	if(b[i] < a[i]) {
		return 1;
	}
	return 0;
}

void calc(int l, int r, vector<int> &v, vector<int> &temp) {
	if(l == r) {
		return;
	}	
	int mid = (l + r) >> 1;
	calc(l, mid, v, temp);
	calc(mid + 1, r, v, temp);
	int timer = l, i = l, j = mid + 1;
	while(i <= mid && j <= r) {
		if(comp(v[i], v[j], sz(v))) {
			temp[timer++] = v[i++];
			continue;
		}
		temp[timer++] = v[j++];
	} 
	for(int k = i; k <= mid; ++k) temp[timer++] = v[k];
	for(int k = j; k <= r; ++k) temp[timer++] = v[k];
	for(int i = l; i <= r; ++i) v[i] = temp[i];	
}

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.
        int n = N;    
        vector<int> v, p;
        for(int i = 1; i <= n; ++i) {
        	v.pb(i - 1);
    	}
    	p = v;
    	calc(0, n - 1, v, p); 
    	for(int i = 0; i < n; ++i) {
    		P[v[i]] = i + 1;
    	}
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
		int n = N, a[n], b[n];
		vector<int> v; 
		for(int t = 0; t < n; ++t) {
			
		}
		for(int i = 0; i < n; ++i) {
    		P[v[i]] = i + 1;
    	}
    }
}

Compilation message (stderr)

koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:137:14: warning: unused variable 'a' [-Wunused-variable]
  137 |   int n = N, a[n], b[n];
      |              ^
koala.cpp:137:20: warning: unused variable 'b' [-Wunused-variable]
  137 |   int n = N, a[n], b[n];
      |                    ^

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