제출 #842426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842426		Tob	코알라 (APIO17_koala)	C++14	100 / 100	49 ms	760 KiB

koala

#include <bits/stdc++.h>
#include "koala.h"

using namespace std;

int minValue(int N, int W) {
    int arr[100] = {0}, r[100];
    arr[0] = 1;
    playRound(arr, r);
    for (int i = 1; i < N; i++) if (r[i] == 0) return i;
    return 0;
}

int maxValue(int N, int W) {
    int arr[100] = {0}, r[100];
    vector <int> v;
    for (int i = 0; i < N; i++) {
        v.push_back(i);
    }
    while (v.size() > 1) {
        for (int i = 0; i < N; i++) arr[i] = 0;
        int siz = v.size();
        for (int i = 0; i < siz; i++) arr[v[i]] = N/siz;
        playRound(arr, r);
        v.clear();
        for (int i = 0; i < N; i++) if (r[i] > N/siz) v.push_back(i);
    }
    return v[0];
}

int greaterValue(int N, int W) {
    int arr[100] = {0}, r[100];
    int lo = 1, hi = 9;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        fill(arr, arr+N, 0);
        arr[0] = arr[1] = mid;
        playRound(arr, r);
        if ((r[0] > mid) != (r[1] > mid)) return (r[0] < r[1]);
        if (r[0] <= mid && r[1] <= mid) hi = mid-1;
        else lo = mid+1;
    }

    return 0;
}

bool Cmp(int x, int y, int N) {
    int arr[100] = {0}, r[100];
    arr[x] = arr[y] = N;
    playRound(arr, r);
    return r[x] < r[y];
}
void Sort(vector <int>& v, int N) {
    int siz = v.size();
    if (siz == 1) return;
    vector <int> a, b;
    for (int i = 0; i < siz/2; i++) a.push_back(v[i]);
    for (int i = siz/2; i < siz; i++) b.push_back(v[i]);
    v.clear();
    Sort(a, N); Sort(b, N);
    //for (int i = 0; i < a.size(); i++) cout << a[i] << " "; cout << " -  ";
    //for (int i = 0; i < b.size(); i++) cout << b[i] << " "; cout << "\n";
    int x = 0, y = 0;
    for (; x < a.size() && y < b.size();) {
        if (Cmp(a[x], b[y], N)) v.push_back(a[x++]);
        else v.push_back(b[y++]);
    }
    for (; x < a.size(); x++) v.push_back(a[x]);
    for (; y < b.size(); y++) v.push_back(b[y]);
    //for (int i = 0; i < v.size(); i++) cout << v[i] << " "; cout << "\n";
}

void rek(vector <int>& v, int N, int W, int lo, int hi) {
    if (lo >= hi) return;
    int sqlo = sqrt(2*lo);
    int x = min(sqlo, W/(hi-lo+1));
    int arr[100] = {0}, r[100];
    for (int i = 0; i < v.size(); i++) arr[v[i]] = x;
    vector <int> a, b;
    playRound(arr, r);
    for (int i = 0; i < v.size(); i++) {
        if (r[v[i]] > x) b.push_back(v[i]);
        else a.push_back(v[i]);
    }
    int mid = lo + a.size();
    rek(a, N, W, lo, mid-1);
    rek(b, N, W, mid, hi);
    v = a;
    for (int i = 0; i < b.size(); i++) v.push_back(b[i]);
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        vector <int> v;
        for (int i = 0; i < N; i++) v.push_back(i);
        Sort(v, N);
        for (int i = 0; i < N; i++) P[v[i]] = i+1;
    } else {
        vector <int> v;
        for (int i = 0; i < N; i++) v.push_back(i);
        rek(v, N, W, 1, N);
        for (int i = 0; i < N; i++) P[v[i]] = i+1;
    }
}

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

koala.cpp: In function 'void Sort(std::vector<int>&, int)':
koala.cpp:64:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (; x < a.size() && y < b.size();) {
      |            ~~^~~~~~~~~~
koala.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (; x < a.size() && y < b.size();) {
      |                            ~~^~~~~~~~~~
koala.cpp:68:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (; x < a.size(); x++) v.push_back(a[x]);
      |            ~~^~~~~~~~~~
koala.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (; y < b.size(); y++) v.push_back(b[y]);
      |            ~~^~~~~~~~~~
koala.cpp: In function 'void rek(std::vector<int>&, int, int, int, int)':
koala.cpp:78:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for (int i = 0; i < v.size(); i++) arr[v[i]] = x;
      |                     ~~^~~~~~~~~~
koala.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
koala.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < b.size(); i++) v.push_back(b[i]);
      |                     ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 53 / 53