제출 #157867

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

koala

#include "koala.h"
#include <bits/stdc++.h>
#define e begin()
#define f end()
#define w vector<int>
using namespace std;
int B[100], R[100];
bool compare(int a, int b, int N, int W) {
fill(B, B + N, 0);
B[a] = B[b] = W;
playRound(B, R);
return (R[b] > W);
}
w g(w v, int N, int W) {
if (v.size() == 1) return v;
w a, b;
a.insert(a.e, v.e, v.e + (v.size() + 1) / 2);
b.insert(b.e, v.e + (v.size() + 1) / 2, v.f);
a = g(a, N, W), b = g(b, N, W);
w s;
int aptr = 0, bptr = 0;
while (aptr < a.size() && bptr < b.size()) {
if (compare(a[aptr], b[bptr], N, W)) s.push_back(a[aptr++]);
else s.push_back(b[bptr++]);
}
s.insert(s.f, a.e + aptr, a.f);
s.insert(s.f, b.e + bptr, b.f);
return s;
}
void q(w v, int N, int W, int* P, int l = 1, int r = 100) {
if (l == r) P[v[0]] = l;
else {
int x = min((int)sqrt(2 * l), W / (r - l + 1));
fill(B, B + N, 0);
for (int i : v) B[i] = x;
playRound(B, R);
w L, G;
for (int i : v) if (R[i] > x) G.push_back(i);
else L.push_back(i);
q(L, N, W, P, l, l + L.size() - 1);
q(G, N, W, P, r - G.size() + 1, r);
}
}
int minValue(int N, int W) {
fill(B, B + N, 0);
B[0] = 1;
playRound(B, R);
if (R[0] < 2) return 0;
else for (int i = 1; i < N; i++) if (!R[i]) return i;
}
int maxValue(int N, int W) {
w v;
for (int i = 0; i < N; i++) v.push_back(i);
while (v.size() != 1) {
int k = W / v.size();
fill(B, B + N, 0);
for (int i : v) B[i] = k;
playRound(B, R);
v.clear();
for (int i = 0; i < N; i++) if (R[i] > k) v.push_back(i);
}
return v[0];
}
int greaterValue(int N, int W) {
int l = 1, r = 9;
while (l != r) {
int m = (l + r) / 2;
B[0] = B[1] = m;
playRound(B, R);
if (R[0] > m && R[1] > m) l = m + 1;
else if (R[0] <= m && R[1] <= m) r = m - 1;
else return (R[0] < R[1]);
}
B[0] = B[1] = l;
playRound(B, R);
return (R[0] < R[1]);
}
void allValues(int N, int W, int *P) {
if (W == 2 * N) {
w v;
for (int i = 0; i < N; i++) v.push_back(i);
w s = g(v, N, W / 2);
for (int i = 0; i < N; i++) P[s[i]] = i + 1;
} else {
w v;
for (int i = 0; i < N; i++) v.push_back(i);
q(v, N, W, P);
}
}

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

koala.cpp: In function 'std::vector<int> g(std::vector<int>, int, int)':
koala.cpp:22:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while (aptr < a.size() && bptr < b.size()) {
        ~~~~~^~~~~~~~~~
koala.cpp:22:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 while (aptr < a.size() && bptr < b.size()) {
                           ~~~~~^~~~~~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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