제출 #981193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
981193		yhkhoo	코알라 (APIO17_koala)	C++17	72 / 100	44 ms	596 KiB

koala

#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);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 53 / 53