Submission #725878

#	Time	Username	Problem	Language	Result	Execution time	Memory
725878		pragmatist	Koala Game (APIO17_koala)	C++17	99 / 100	88 ms	340 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 * tr), 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:18: warning: unused variable 'a' [-Wunused-variable]
  175 |       int n = N, a[n], b[n];
      |                  ^
koala.cpp:175:24: 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: 52 / 53