oj.uz

Submission #544812

# Submission time Handle Problem Language Result Execution time Memory
544812 2022-04-02T18:42:16 Z amunduzbaev Koala Game (APIO17_koala) C++17
86 / 100
 87 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) {
	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) 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] {};
		if(W == 2 * N){
			for(int i=0;i<N;i++) B[i] = 1;
		}
		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 316 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 17 ms 208 KB Output is correct
2 Correct 13 ms 316 KB Output is correct
3 Correct 14 ms 320 KB Output is correct
4 Correct 17 ms 208 KB Output is correct

Subtask #3
14.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 73 ms 324 KB Output is partially correct
2 Partially correct 87 ms 324 KB Output is partially correct
3 Partially correct 83 ms 332 KB Output is partially correct
4 Partially correct 62 ms 320 KB Output is partially correct
5 Partially correct 79 ms 440 KB Output is partially correct
6 Partially correct 71 ms 324 KB Output is partially correct
7 Partially correct 68 ms 328 KB Output is partially correct
8 Partially correct 66 ms 332 KB Output is partially correct
9 Partially correct 60 ms 312 KB Output is partially correct
10 Partially correct 66 ms 328 KB Output is partially correct

Subtask #4
0 / 10.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 -

Subtask #5
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 208 KB Output is correct
2 Correct 3 ms 208 KB Output is correct
3 Correct 4 ms 208 KB Output is correct
4 Correct 3 ms 316 KB Output is correct
5 Correct 3 ms 208 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 4 ms 208 KB Output is correct
8 Correct 4 ms 208 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 320 KB Output is correct
12 Correct 3 ms 316 KB Output is correct
13 Correct 4 ms 208 KB Output is correct
14 Correct 3 ms 208 KB Output is correct
15 Correct 5 ms 208 KB Output is correct
16 Correct 4 ms 208 KB Output is correct
17 Correct 4 ms 208 KB Output is correct
18 Correct 4 ms 208 KB Output is correct
19 Correct 4 ms 208 KB Output is correct
20 Correct 4 ms 208 KB Output is correct
21 Correct 4 ms 208 KB Output is correct
22 Correct 4 ms 208 KB Output is correct
23 Correct 5 ms 320 KB Output is correct
24 Correct 4 ms 208 KB Output is correct
25 Correct 3 ms 208 KB Output is correct
26 Correct 3 ms 208 KB Output is correct
27 Correct 3 ms 208 KB Output is correct
28 Correct 3 ms 208 KB Output is correct
29 Correct 3 ms 208 KB Output is correct
30 Correct 5 ms 208 KB Output is correct
31 Correct 3 ms 208 KB Output is correct
32 Correct 3 ms 328 KB Output is correct
33 Correct 3 ms 316 KB Output is correct
34 Correct 4 ms 208 KB Output is correct
35 Correct 4 ms 320 KB Output is correct
36 Correct 3 ms 208 KB Output is correct
37 Correct 3 ms 208 KB Output is correct
38 Correct 4 ms 212 KB Output is correct
39 Correct 4 ms 208 KB Output is correct
40 Correct 4 ms 208 KB Output is correct