oj.uz

Submission #544805

# Submission time Handle Problem Language Result Execution time Memory
544805 2022-04-02T18:30:33 Z amunduzbaev Koala Game (APIO17_koala) C++17
33 / 100
 73 ms 464 KB 
#include "koala.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif

int minValue(int N, int W) {
	int B[N] {}, R[N] {};
	B[0] = 1;
	playRound(B, R);
	for(int i=0;i<N;i++){
		if(R[i] > B[i]) continue;
		else return i;
	} assert(false);
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    return 0;
}

int maxValue(int N, int W) {
	vector<int> p(N);
	for(int i=0;i<N;i++) p[i] = i;
	while((int)p.size() > 1){
		int v = W / (int)p.size();
		int B[N] {}, R[N] {};
		for(auto x : p) B[x] = v;
		playRound(B, R);
		vector<int> t;
		for(auto x : p){
			if(B[x] < R[x]){
				t.push_back(x);
			}
		}
		
		swap(p, t);
	}
	
	assert((int)p.size() == 1);
	return p[0];
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    return 0;
}

int greaterValue(int N, int W) {
	int is = -1;
	auto ask = [&](int v){
		int B[N] {}, R[N] {};
		B[0] = B[1] = v;
		playRound(B, R);
		int c = (R[0] > B[0]) + (R[1] > B[1]);
		if(c == 1){
			if(R[0] > B[0]) is = 0;
			else is = 1;
		} return c;
	};
	
	int l = 1, r = 8;
	while(l < r){
		int m = (l + r) >> 1;
		int v = ask(m);
		if(v == 1) break;
		if(v == 2) l = m + 1;
		else r = m - 1;
	}
	
	if(~is) return is;
	assert(l == r);
	ask(l);
	return is;
	
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    return 0;
}

#define ar array

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.
        assert(false);
    } else {
		vector<int> pref(N + 1);
		for(int i=1;i<=N;i++){
			pref[i] = pref[i-1] + i;
		}
		
		auto check = [&](int l, int r, int v){
			ar<int, 2> mx {-1, -1};
			int lef = r;
			for(int x=0;x<=(r - l + 1);x++){
				if(x * (v + 1) > lef) continue;
				int res = pref[N] - pref[r];
				res += (pref[r] - pref[r - x]);
				int rem = lef - x * (v + 1);
				res += (pref[l - 1] - pref[max(0, l - 1 - rem)]);
				mx = max(mx, {res, x});
			}
			
			assert(~mx[1]);
			return mx[1];
		};
		
		auto ask = [&](vector<int> p, int v) -> ar<vector<int>, 2>{
			int B[N] {}, R[N] {};
			for(auto x : p) B[x] = v;
			playRound(B, R);
			ar<vector<int>, 2> t;
			for(auto x : p){
				if(B[x] < R[x]) t[1].push_back(x);
				else t[0].push_back(x);
			} return t;
		};
		
		int cnt = 0;
		
		function<void(int, int, vector<int>)> go = [&](int l, int r, vector<int> p){
			//~ assert(r - l + 1 == (int)p.size());
			if(l == r){
				//~ assert((int)p.size() == 1);
				P[p[0]] = l;
				return;
			}
			
			//~ cout<<l<<" "<<r<<endl;
			
			int h = (r - l + 1) >> 1;
			int lx = 1, rx = r / (r - l + 1);
			while(lx < rx){
				int m = (lx + rx) >> 1;
				int y = check(l, r, m);
				if(y <= h) rx = m;
				else lx = m + 1;
			}
			
			if(lx > 1){
				int y1 = check(l, r, lx);
				int y2 = check(l, r, lx - 1);
				if(abs(y1 - h) <= abs(y2 - h)){
					ar<vector<int>, 2> t = ask(p, lx);
					assert(y1 == (int)t[1].size());
					int m = r - y1; cnt++;
					go(l, m, t[0]);
					go(m + 1, r, t[1]);
				} else {
					ar<vector<int>, 2> t = ask(p, lx + 1);
					assert(y2 == (int)t[1].size());
					int m = r - y2; cnt++;
					go(l, m, t[0]);
					go(m + 1, r, t[1]);
				}
			} else {
				ar<vector<int>, 2> t = ask(p, lx);
				int y = check(l, r, lx);
				assert(y == (int)t[1].size());
				int m = r - y; cnt++;
				go(l, m, t[0]);
				go(m + 1, r, t[1]);
			}
		};
		
		vector<int> p(N);
		iota(p.begin(), p.end(), 0);
		go(1, N, p);
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 4 ms 208 KB Output is correct
3 Correct 4 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 316 KB Output is correct
2 Correct 12 ms 312 KB Output is correct
3 Correct 11 ms 208 KB Output is correct
4 Correct 12 ms 312 KB Output is correct

Subtask #3
14.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 66 ms 208 KB Output is partially correct
2 Partially correct 73 ms 208 KB Output is partially correct
3 Partially correct 57 ms 336 KB Output is partially correct
4 Partially correct 54 ms 320 KB Output is partially correct
5 Partially correct 56 ms 328 KB Output is partially correct
6 Partially correct 61 ms 336 KB Output is partially correct
7 Partially correct 55 ms 324 KB Output is partially correct
8 Partially correct 58 ms 324 KB Output is partially correct
9 Partially correct 56 ms 312 KB Output is partially correct
10 Partially correct 57 ms 332 KB Output is partially correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 464 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -