| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 66670 | nvmdava | 저울 (IOI15_scales) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
struct pos{
int send[6], sort[7], mn[7][7][7], mx[7][7][7], md[7][7][7], qr[7][7][7][7];
void fill(){
for(int i = 0; i <= 5; i++){
sort[send[i]] = i;
}
vector<int> tmp(3, 0);
int mnm,mxm,mdm, a;
for(int i = 1; i < 5; i++){
tmp[0] = i;
for(int j = i + 1; j < 6; j++){
tmp[1] = j;
for(int l = j + 1; l <= 6; l++){
tmp[2] = l;
if(sort[i] < sort[j] && sort[j] < sort[l]){
mnm = i;
mdm = j;
mxm = l;
} else if(sort[i] < sort[l] && sort[l] < sort[j]){
mnm = i;
mdm = l;
mxm = j;
} else if(sort[j] < sort[i] && sort[i] < sort[l]){
mnm = j;
mdm = i;
mxm = l;
} else if(sort[j] < sort[l] && sort[l] < sort[i]){
mnm = j;
mdm = l;
mxm = i;
} else if(sort[l] < sort[i] && sort[i] < sort[j]){
mnm = l;
mdm = i;
mxm = j;
} else {
mnm = l;
mdm = j;
mxm = i;
}
do{
mn[tmp[0]][tmp[1]][tmp[2]] = mnm;
mx[tmp[0]][tmp[1]][tmp[2]] = mxm;
md[tmp[0]][tmp[1]][tmp[2]] = mdm;
} while(next_permutation(tmp.begin(), tmp.end()));
for(int t = 1; t <= 6; t++){
if(i == t || t == j || t == l){
continue;
}
if(sort[t] < sort[mnm]){
a = mnm;
} else if(sort[t] < sort[mdm]){
a = mdm;
} else if(sort[t] < sort[mxm]){
a = mxm;
} else {
a = mnm;
}
do{
qr[tmp[0]][tmp[1]][tmp[2]][t] = a;
} while(next_permutation(tmp.begin(), tmp.end()));
}
}
}
}
}
};
pos all[720];
vector<pos> v;
vector<int> tmp = {1, 2, 3, 4, 5, 6};
void init(int T) {
int s = 0;
do{
for(int i = 0; i < 5; i++){
all[s].send[i] = tmp[i];
}
all[s].fill();
s++;
} while(next_permutation(tmp.begin(), tmp.end()));
}
void orderCoins() {
v.insert(v.begin(), all + 0, all + 720);
answer(v[0]);
return;
while(v.size() != 1){
int A, B, C, D, res[4], dif = 1001, type = 0;
//Find best query;
for(int i = 1; i < 5; i++){
for(int j = i + 1; j < 6; j++){
for(int l = j + 1; l <= 6; l++){
memset(res, 0, sizeof(res));
for(auto x : v){
if(x.mn[i][j][l] == i){
res[1]++;
} else if(x.mn[i][j][l] == j){
res[2]++;
} else {
res[0]++;
}
}
if(dif > max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]))){
dif = max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]));
type = 1;
A = i;
B = j;
C = l;
}
}
}
}
for(int i = 1; i < 5; i++){
for(int j = i + 1; j < 6; j++){
for(int l = j + 1; l <= 6; l++){
memset(res, 0, sizeof(res));
for(auto x : v){
if(x.md[i][j][l] == i){
res[1]++;
} else if(x.md[i][j][l] == j){
res[2]++;
} else {
res[0]++;
}
}
if(dif > max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]))){
dif = max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]));
type = 2;
A = i;
B = j;
C = l;
}
}
}
}
for(int i = 1; i < 5; i++){
for(int j = i + 1; j < 6; j++){
for(int l = j + 1; l <= 6; l++){
memset(res, 0, sizeof(res));
for(auto x : v){
if(x.mx[i][j][l] == i){
res[1]++;
} else if(x.mx[i][j][l] == j){
res[2]++;
} else {
res[0]++;
}
}
if(dif > max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]))){
dif = max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]));
type = 3;
A = i;
B = j;
C = l;
}
}
}
}
for(int i = 1; i < 5; i++){
for(int j = i + 1; j < 6; j++){
for(int l = j + 1; l <= 6; l++){
for(int t = 1; t <= 6; t++){
if(t == i || t == j || t == l){
continue;
}
memset(res, 0, sizeof(res));
for(auto x : v){
if(x.qr[i][j][l][t] == i){
res[1]++;
} else if(x.qr[i][j][l][t] == j){
res[2]++;
} else {
res[0]++;
}
}
if(dif > max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]))){
dif = max(res[0], max(res[1], res[2])) - min(res[0], min(res[1], res[2]));
type = 4;
A = i;
B = j;
C = l;
D = t;
}
}
}
}
}
//Ask best query;
if(type == 1){
res[0] = getLightest(A, B, C);
for(int i = 0; i < v.size(); i++){
if(v[i].mn[A][B][C] != res[0]){
v.erase(v.begin() + i);
i--;
}
}
} else if(type == 2){
res[0] = getMedian(A, B, C);
for(int i = 0; i < v.size(); i++){
if(v[i].md[A][B][C] != res[0]){
v.erase(v.begin() + i);
i--;
}
}
} else if(type == 3){
res[0] = getHeaviest(A, B, C);
for(int i = 0; i < v.size(); i++){
if(v[i].mx[A][B][C] != res[0]){
v.erase(v.begin() + i);
i--;
}
}
} else {
res[0] = getNextLightest(A, B, C, D);
for(int i = 0; i < v.size(); i++){
if(v[i].qr[A][B][C][D] != res[0]){
v.erase(v.begin() + i);
i--;
}
}
}
}
answer(v[0].send);
}