| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 584916 | Jomnoi | 저울 (IOI15_scales) | C++17 | 23 ms | 348 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
const int INF = 1e9 + 7;
int possible;
vector <int> perm[720];
bool cantuse[720];
void init(int T) {
vector <int> arr({1, 2, 3, 4, 5, 6});
int cnt = 0;
do {
perm[cnt] = arr;
cnt++;
} while(next_permutation(arr.begin(), arr.end()));
}
int findHeaviest(int A, int B, int C) {
return max({A, B, C});
}
int findLightest(int A, int B, int C) {
return min({A, B, C});
}
int findMedian(int A, int B, int C) {
int ma = max({A, B, C}), mi = min({A, B, C});
if(A != ma and A != mi) {
return A;
}
if(B != ma and B != mi) {
return B;
}
if(C != ma and C != mi) {
return C;
}
return -1;
}
int findNextLightest(int A, int B, int C, int D) {
int upb = INF;
if(A > D) {
upb = min(upb, A);
}
if(B > D) {
upb = min(upb, B);
}
if(C > D) {
upb = min(upb, C);
}
if(upb == INF) {
upb = min({A, B, C});
}
return upb;
}
void orderCoins() {
possible = 720;
memset(cantuse, false, sizeof(cantuse));
while(possible > 1) {
int optLeft = INF;
int A, B, C, D, type;
int tmp, remain, result;
int hi, hj, hk, li, lj, lk, mi, mj, mk, nli, nlj, nlk;
for(int i = 0; i < 6; i++) {
for(int j = i + 1; j < 6; j++) {
for(int k = j + 1; k < 6; k++) {
hi = 0, hj = 0, hk = 0;
li = 0, lj = 0, lk = 0;
mi = 0, mj = 0, mk = 0;
for(int p = 0; p < 720; p++) {
if(cantuse[p] == true) {
continue;
}
tmp = findHeaviest(perm[p][i], perm[p][j], perm[p][k]);
if(tmp == perm[p][i]) {
hi++;
}
if(tmp == perm[p][j]) {
hj++;
}
if(tmp == perm[p][k]) {
hk++;
}
tmp = findLightest(perm[p][i], perm[p][j], perm[p][k]);
if(tmp == perm[p][i]) {
li++;
}
if(tmp == perm[p][j]) {
lj++;
}
if(tmp == perm[p][k]) {
lk++;
}
tmp = findMedian(perm[p][i], perm[p][j], perm[p][k]);
if(tmp == perm[p][i]) {
mi++;
}
if(tmp == perm[p][j]) {
mj++;
}
if(tmp == perm[p][k]) {
mk++;
}
}
remain = max({hi, hj, hk});
if(remain < optLeft) {
optLeft = remain;
A = i, B = j, C = k;
type = 1;
}
remain = max({li, lj, lk});
if(remain < optLeft) {
optLeft = remain;
A = i, B = j, C = k;
type = 2;
}
remain = max({mi, mj, mk});
if(remain < optLeft) {
optLeft = remain;
A = i, B = j, C = k;
type = 3;
}
for(int l = 0; l < 6; l++) {
if(l == i or l == j or l == k) {
continue;
}
nli = 0, nlj = 0, nlk = 0;
for(int p = 0; p < 720; p++) {
if(cantuse[p] == true) {
continue;
}
tmp = findNextLightest(perm[p][i], perm[p][j], perm[p][k], perm[p][l]);
if(tmp == perm[p][i]) {
nli++;
}
if(tmp == perm[p][j]) {
nlj++;
}
if(tmp == perm[p][k]) {
nlk++;
}
}
remain = max({nli, nlj, nlk});
if(remain < optLeft) {
optLeft = remain;
A = i, B = j, C = k, D = l;
type = 4;
}
}
}
}
}
if(type == 1) {
result = getHeaviest(A + 1, B + 1, C + 1) - 1;
for(int p = 0; p < 720; p++) {
if(cantuse[p] == true) {
continue;
}
if(findHeaviest(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
cantuse[p] = true;
possible--;
}
}
}
else if(type == 2) {
result = getLightest(A + 1, B + 1, C + 1) - 1;
for(int p = 0; p < 720; p++) {
if(cantuse[p] == true) {
continue;
}
if(findLightest(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
cantuse[p] = true;
possible--;
}
}
}
else if(type == 3) {
result = getMedian(A + 1, B + 1, C + 1) - 1;
for(int p = 0; p < 720; p++) {
if(cantuse[p] == true) {
continue;
}
if(findMedian(perm[p][A], perm[p][B], perm[p][C]) != perm[p][result]) {
cantuse[p] = true;
possible--;
}
}
}
else if(type == 4) {
result = getNextLightest(A + 1, B + 1, C + 1, D + 1) - 1;
for(int p = 0; p < 720; p++) {
if(cantuse[p] == true) {
continue;
}
if(findNextLightest(perm[p][A], perm[p][B], perm[p][C], perm[p][D]) != perm[p][result]) {
cantuse[p] = true;
possible--;
}
}
}
}
int W[6];
for(int p = 0; p < 720; p++) {
if(cantuse[p] == false) {
for(int i = 0; i < 6; i++) {
W[perm[p][i] - 1] = i + 1;
}
}
}
answer(W);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||