| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1261205 | kl0989e | Scales (IOI15_scales) | C++20 | 31 ms | 472 KiB |
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()
void init(int t) {}
void orderCoins() {
/*int mn1=getLightest(1,2,3);
int mn2=getLightest(4,5,6);
int ans[6];
ans[5]=0;
ans[0]=getLightest(mn1,mn2,1+(mn1==1 || mn2==1)+((mn1==2 || mn2==2) && (mn1==1 || mn2==1)));
if (ans[0]==mn1) {
ans[1]=getLightest(mn2,(mn1==1?2:1),(mn1==3?2:3));
}
else {
ans[1]=getLightest(mn1,(mn2==4?5:4),(mn2==6?5:6));
}
if ((mn1==ans[0] && mn2==ans[1]) || (mn2==ans[0] && mn1==ans[1])) {
vi rem={1,2,3,4,5,6};
rem.erase(find(all(rem),ans[0]));
rem.erase(find(all(rem),ans[1]));
int mn3=getLightest(rem[0],rem[1],rem[2]);
ans[2]=getMedian(mn1,mn3,rem[3]);
if (ans[2]==rem[3]) {
ans[3]=mn3;
ans[4]=getMedian(rem[0],rem[1],rem[2]);
ans[5]=21-accumulate(ans,ans+6,0);
answer(ans);
return;
}
}
else if (mn1==ans[0]) {
ans[2]=getMedian(mn1,mn2,6-ans[0]-ans[1]);
}
else {
ans[2]=getMedian(mn1,mn2,15-ans[0]-ans[1]);
}
vi rem={1,2,3,4,5,6};
rem.erase(find(all(rem),ans[0]));
rem.erase(find(all(rem),ans[1]));
rem.erase(find(all(rem),ans[2]));
ans[3]=getLightest(rem[0],rem[1],rem[2]);
ans[4]=getMedian(rem[0],rem[1],rem[2]);
ans[5]=21-accumulate(ans,ans+6,0);
answer(ans);*/
vector<vi> anses(720);
vi t={1,2,3,4,5,6};
for (int i=0; i<720; i++) {
anses[i]=t;
next_permutation(all(t));
}
while (anses.size()>1) {
vi q;
int sze=anses.size();
for (int cn=1; cn<=3; cn++) {
for (int a=1; a<=6; a++) {
for (int b=a+1; b<=6; b++) {
for (int c=b+1; c<=6; c++) {
int aa=0,bb=0,cc=0;
for (auto t:anses) {
int cnt=0;
for (int i=0; i<6; i++) {
if (t[i]==a) {
cnt++;
if (cnt==cn) {
aa++;
break;
}
}
else if (t[i]==b) {
cnt++;
if (cnt==cn) {
bb++;
break;
}
}
else if (t[i]==c) {
cnt++;
if (cnt==cn) {
cc++;
break;
}
}
}
}
if (max(aa,max(bb,cc))<sze) {
sze=max(aa,max(bb,cc));
q={cn,a,b,c};
}
}
}
}
}
for (int a=1; a<=6; a++) {
for (int b=a+1; b<=6; b++) {
for (int c=b+1; c<=6; c++) {
for (int d=c+1; d<=6; d++) {
int aa=0,bb=0,cc=0;
for (auto t:anses) {
bool act=0;
for (int i=0; ; i=(i+1)%6) {
if (t[i]==d) {
act=1;
}
else if (t[i]==a && act) {
aa++;
break;
}
else if (t[i]==b && act) {
bb++;
break;
}
else if (t[i]==c && act) {
cc++;
break;
}
}
}
if (max(aa,max(bb,cc))<sze) {
sze=max(aa,max(bb,cc));
q={4,a,b,c,d};
}
}
}
}
}
if (q[0]!=4) {
int resp;
int cn=q[0],a=q[1],b=q[2],c=q[3];
if (cn==1) {
resp=getLightest(a,b,c);
}
else if (cn==2) {
resp=getMedian(a,b,c);
}
else {
resp=getHeaviest(a,b,c);
}
vector<vi> newanses;
for (auto t:anses) {
int cnt=0;
for (int i=0; i<6; i++) {
if (t[i]==a) {
cnt++;
if (cnt==cn) {
if (resp==a) {
newanses.pb(t);
}
break;
}
}
else if (t[i]==b) {
cnt++;
if (cnt==cn) {
if (resp==b) {
newanses.pb(t);
}
break;
}
}
else if (t[i]==c) {
cnt++;
if (cnt==cn) {
if (resp==c) {
newanses.pb(t);
}
break;
}
}
}
}
swap(anses,newanses);
}
else {
int a=q[1],b=q[2],c=q[3],d=q[4];
int resp=getNextLightest(a,b,c,d);
vector<vi> newanses;
for (auto t:anses) {
bool act=0;
for (int i=0; ; i=(i+1)%6) {
if (t[i]==d) {
act=1;
}
else if (t[i]==a && act) {
if (resp==a) {
newanses.pb(t);
}
break;
}
else if (t[i]==b && act) {
if (resp==b) {
newanses.pb(t);
}
break;
}
else if (t[i]==c && act) {
if (resp==c) {
newanses.pb(t);
}
break;
}
}
}
swap(anses,newanses);
}
}
int ans[6];
for (int i=0; i<6; i++) {
ans[i]=anses[0][i];
}
answer(ans);
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||