oj.uz

Submission #544906

# Submission time Handle Problem Language Result Execution time Memory
544906 2022-04-03T06:16:12 Z amunduzbaev Koala Game (APIO17_koala) C++17
96 / 100
 72 ms 344 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) {
	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 = W - (N - r);
		for(int x=0;x<=(r - l + 1);x++){
			if(x * (v + 1) > lef) break;
			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)]);
			if(mx[0] < res) mx = {res, x};
			//~ 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;
		}
		
		int h = (r - l + 1) >> 1;
		int lx = 1, rx = (W - N + 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 316 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 320 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
14.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 60 ms 312 KB Output is partially correct
2 Partially correct 72 ms 324 KB Output is partially correct
3 Partially correct 59 ms 324 KB Output is partially correct
4 Partially correct 64 ms 324 KB Output is partially correct
5 Partially correct 61 ms 324 KB Output is partially correct
6 Partially correct 60 ms 336 KB Output is partially correct
7 Partially correct 59 ms 344 KB Output is partially correct
8 Partially correct 59 ms 328 KB Output is partially correct
9 Partially correct 57 ms 328 KB Output is partially correct
10 Partially correct 58 ms 332 KB Output is partially correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 7 ms 208 KB Output is correct
3 Correct 6 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 6 ms 208 KB Output is correct
6 Correct 5 ms 208 KB Output is correct
7 Correct 6 ms 208 KB Output is correct
8 Correct 6 ms 332 KB Output is correct
9 Correct 5 ms 208 KB Output is correct
10 Correct 6 ms 208 KB Output is correct
11 Correct 5 ms 208 KB Output is correct
12 Correct 6 ms 328 KB Output is correct
13 Correct 6 ms 208 KB Output is correct
14 Correct 6 ms 324 KB Output is correct
15 Correct 8 ms 328 KB Output is correct
16 Correct 6 ms 208 KB Output is correct
17 Correct 6 ms 208 KB Output is correct
18 Correct 6 ms 208 KB Output is correct
19 Correct 6 ms 208 KB Output is correct
20 Correct 6 ms 292 KB Output is correct

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 3 ms 208 KB Output is correct
6 Correct 3 ms 208 KB Output is correct
7 Correct 4 ms 324 KB Output is correct
8 Correct 3 ms 324 KB Output is correct
9 Correct 3 ms 208 KB Output is correct
10 Correct 4 ms 208 KB Output is correct
11 Correct 4 ms 208 KB Output is correct
12 Correct 4 ms 208 KB Output is correct
13 Correct 3 ms 208 KB Output is correct
14 Correct 3 ms 208 KB Output is correct
15 Correct 3 ms 208 KB Output is correct
16 Correct 3 ms 208 KB Output is correct
17 Correct 3 ms 208 KB Output is correct
18 Correct 3 ms 208 KB Output is correct
19 Correct 3 ms 208 KB Output is correct
20 Correct 3 ms 208 KB Output is correct
21 Correct 3 ms 208 KB Output is correct
22 Correct 3 ms 208 KB Output is correct
23 Correct 4 ms 208 KB Output is correct
24 Correct 3 ms 256 KB Output is correct
25 Correct 4 ms 320 KB Output is correct
26 Correct 3 ms 208 KB Output is correct
27 Correct 4 ms 208 KB Output is correct
28 Correct 5 ms 208 KB Output is correct
29 Correct 3 ms 208 KB Output is correct
30 Correct 3 ms 208 KB Output is correct
31 Correct 3 ms 208 KB Output is correct
32 Correct 3 ms 320 KB Output is correct
33 Correct 3 ms 208 KB Output is correct
34 Correct 3 ms 208 KB Output is correct
35 Correct 3 ms 208 KB Output is correct
36 Correct 3 ms 208 KB Output is correct
37 Correct 3 ms 208 KB Output is correct
38 Correct 3 ms 208 KB Output is correct
39 Correct 3 ms 208 KB Output is correct
40 Correct 3 ms 208 KB Output is correct