oj.uz

Submission #981193

# Submission time Handle Problem Language Result Execution time Memory
981193 2024-05-13T01:55:59 Z yhkhoo Koala Game (APIO17_koala) C++17
72 / 100
 44 ms 596 KB 
#include "koala.h"
#include <bits/stdc++.h>
using namespace std;

int B[100], R[100];

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.
    memset(B, 0, 100*sizeof(int));
    *B = 1;
    playRound(B, R);
    for(int i=0; i<100; i++){
		if(i[R] <= i[B]){
			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 B[100], R[100];
	fill(B, B+100, 1);
	playRound(B, R);
	for(int i=0; i<100; i++){
		if(i[R] > i[B]){
			i[B] = 2;
		}
		else{
			i[B] = 0;
		}
	}
	playRound(B, R);
	for(int i=0; i<100; i++){
		if(i[B] == 2 && i[R] > i[B]){
			i[B] = 4;
		}
		else{
			i[B] = 0;
		}
	}
	playRound(B, R);
	for(int i=0; i<100; i++){
		if(i[B] == 4 && i[R] > i[B]){
			i[B] = 11;
		}
		else{
			i[B] = 0;
		}
	}
	playRound(B, R);
	for(int i=0; i<100; i++){
		if(i[B] == 11 && i[R] > i[B]){
			return i;
		}
	}
    return -1;
}

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.
    int s = 1, e = 9, m;
    while(s < e){
		m = (s+e)/2;
		memset(B, 0, 100*sizeof(int));
		B[0] = m;
		B[1] = m;
		playRound(B, R);
		if(B[0] > R[0] && B[1] > R[1]){
			e = m-1;
		}
		else if(B[0] <= R[0] && B[1] <= R[1]){
			s = m+1;
		}
		else{
			return R[0] < R[1];
		}
	}
    return -1;
}

#define pb push_back
#define mp make_pair
#define fi first
#define se second
int tcn, cnt;

int xmm[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 3, 1, 3, 1, 1, 2, 3, 4, 2, 3, 4, 4, 1, 2, 3, 3, 4, 1, 5, 1, 2, 2, 3, 5, 3, 4, 5, 2, 5, 2, 3, 4, 5, 4, 4, 6, 1, 2, 3, 5, 6, 3, 4, 6, 5, 6, 1, 4, 5, 6, 1, 7, 1, 2, 2, 2, 3, 4, 5, 7, 3, 4, 7, 5, 6, 7, 2, 5, 6, 7, 2, 2, 3, 4, 5, 6, 8, 3, 4, 6, 8, 5, 8, 6, 8};

pair<vector<int>, vector<int>> touch(const vector<int> &c){
	if(c.size() == 1){
		vector<int> b;
		return mp(c, b);
	}
	for(int x = xmm[tcn]; x <= xmm[tcn]; x++){
		memset(B, 0, 100*sizeof(int));
		for(int i: c){
			B[i] = x;
		}
		playRound(B, R);
		vector<bool> cool(100, 0);
		int kk = 0;
		for(int i: c){
			if(R[i] > B[i]){
				cool[i] = 1;
				kk++;
			}
		}
		if(kk != c.size() && kk != 0){
			//cerr << x << ", ";
			tcn++;
			vector<int> a, b;
			for(int i: c){
				if(cool[i]){
					b.pb(i);
				}
				else{
					a.pb(i);
				}
			}
			return mp(a, b);
		}
	}
	cerr << "\nwtf\n";
	vector<int> v;
	return mp(v,v);
}

void consider(int *P, const vector<int> &a, const vector<int> &b){
	/*if(a.size()) for(int i: a){
		cerr << i << ' ';
	}
	cerr << '\n';
	if(b.size()) for(int i: b){
		cerr << i << ' ';
	}
	cerr << '\n' << '\n';*/
	if(a.size() == 1){
		P[a[0]] = ++cnt;
	}
	if(a.size() > 1){
		auto v1 = touch(a);
		consider(P, v1.fi, v1.se);
	}
	if(b.size()){
		auto v2 = touch(b);
		consider(P, v2.fi, v2.se);
	}
}

void allValues(int N, int W, int *P) {
    if (W == 2*100) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        for(int i=0; i<100; i++){
			P[i] = i+1;
		}
		
		stable_sort(P, P+100, [](int a, int b){
			a--; b--;
			memset(B, 0, 100*sizeof(int));
			B[a] = 100; B[b] = 100;
			playRound(B, R);
			return R[a] < 100;
		});
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        tcn = 0; cnt = 0;
        vector<int> v;
        vector<int> oh;
        oh.reserve(100);
        for(int i=0; i<100; i++){
			oh.pb(i);
		}
		consider(P, oh, v);
    }
}

Compilation message

koala.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > touch(const std::vector<int>&)':
koala.cpp:115:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   if(kk != c.size() && kk != 0){
      |      ~~~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB Output is correct
2 Correct 10 ms 464 KB Output is correct
3 Correct 10 ms 456 KB Output is correct
4 Correct 10 ms 344 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 344 KB Output is correct
2 Incorrect 36 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
53.0 / 53.0

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