Submission #725865

#	Time	Username	Problem	Language	Result	Execution time	Memory
725865		pragmatist	Koala Game (APIO17_koala)	C++17	100 / 100	63 ms	356 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];
}

bool cmp(int i, int j, int n, int W) {
	int 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[i] = a[j] = mid;
		playRound(a, b);   
		if(a[i] >= b[i] && a[j] >= b[j]) {
			r = mid - 1;
			continue;
		}
		bool c = (a[i] < b[i]), d = (a[j] < b[j]);
		if(c && d) {
			l = mid + 1;  
			continue;
		}
		ans = (c < d);
		break;
	}
	assert(ans != -1);
	return ans;	
}

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.
    return cmp(0, 1, N, W);
}

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, int n, int w) {
	if(l == r) {
		return;
	}	
	int mid = (l + r) >> 1;
	calc(l, mid, v, temp, n, w);
	calc(mid + 1, r, v, temp, n, w);
	int timer = l, i = l, j = mid + 1;
	while(i <= mid && j <= r) {
		if((w == 2 * n ? comp(v[i], v[j], sz(v)) : cmp(v[i], v[j], n, w))) {
			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];	
}

int timer;

vector<int> solve(vector<int> &v, int tl, int tr, int n, int W) {
	if(sz(v) <= 1 || tl > tr) {
		return v;
	}
	int c = min((int)sqrt(2 * tl), W / sz(v));
	int a[n], b[n];
	memset(a, 0, sizeof(a));
	for(auto x : v) {
		a[x] = c;
	}
	playRound(a, b);
	vector<int> l, r;
	for(auto x : v) {
		if(a[x] < b[x]) {
			r.pb(x);
		} else {
			l.pb(x);
		}
	}
	if(l.empty() || r.empty()) {
		vector<int> op = v;
		calc(0, sz(v) - 1, v, op, n, W);
		return v;		
	}
	l = solve(l, tl, tl + sz(l) - 1, n, W);
	r = solve(r, tl + sz(l), tr, n, W);
	for(auto x : r) {
		l.pb(x);
	}
	return l;
}

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, N, W); 
    	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) {
			v.pb(t);
		}
		v = solve(v, 1, n, n, W);
		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:175:14: warning: unused variable 'a' [-Wunused-variable]
  175 |   int n = N, a[n], b[n];
      |              ^
koala.cpp:175:20: warning: unused variable 'b' [-Wunused-variable]
  175 |   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: 53 / 53