# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
588620 |
2022-07-03T17:05:53 Z |
sofapuden |
Scales (IOI15_scales) |
C++14 |
|
498 ms |
512 KB |
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
struct node {
int a, b, c, d, t;
node () {}
node (int _a, int _b, int _c, int _d, int _t) : a(_a), b(_b), c(_c), d(_d), t(_t) {}
node (int _a, int _b, int _c, int _t) : node(_a,_b,_c,0,_t) {}
};
vector<vector<int>> perm;
vector<node> Q;
int med(int a, int b, int c){
if(a != max({a,b,c}) && a != min({a,b,c}))return a;
if(b != max({a,b,c}) && b != min({a,b,c}))return b;
if(c != max({a,b,c}) && c != min({a,b,c}))return c;
return 0;
}
int nxl(int a, int b, int c, int d){
vector<int> cu;
cu.push_back(a);
cu.push_back(b);
cu.push_back(c);
cu.push_back(d);
sort(cu.begin(),cu.end());
for(int i = 0; i < 4; ++i)
if(cu[i] == d)return cu[(i+1)%4];
return 0;
}
void init(int T) {
if(!T){
return;
}
vector<int> ini = {0,1,2,3,4,5};
do {
perm.push_back(ini);
}while(next_permutation(ini.begin(),ini.end()));
for(int i = 0; i < 6; ++i){
for(int j = i+1; j < 6; ++j){
for(int k = j+1; k < 6; ++k){
Q.push_back(node(i,j,k,0));
Q.push_back(node(i,j,k,1));
Q.push_back(node(i,j,k,2));
}
}
}
for(int z = 0; z < 6; ++z){
for(int i = 0; i < 6; ++i){
for(int j = i+1; j < 6; ++j){
for(int k = j+1; k < 6; ++k){
if(z == i || z == j || z == k)continue;
Q.push_back(node(i,j,k,z,3));
}
}
}
}
/* ... */
}
void orderCoins() {
vector<vector<int>> curperm = perm;
while(curperm.size() > 1){
int bes = 1000;
node que(0,0,0,0);
for(auto x : Q){
if(x.t == 0){
int A = 0, B = 0, C = 0;
for(auto y : curperm){
if(y[x.a] == max({y[x.a],y[x.b],y[x.c]}))A++;
if(y[x.b] == max({y[x.a],y[x.b],y[x.c]}))B++;
if(y[x.c] == max({y[x.a],y[x.b],y[x.c]}))C++;
}
A = max({A,B,C});
if(A <= bes){
bes = A;
que = x;
}
}
else if(x.t == 1){
int A = 0, B = 0, C = 0;
for(auto y : curperm){
if(y[x.a] == min({y[x.a],y[x.b],y[x.c]}))A++;
if(y[x.b] == min({y[x.a],y[x.b],y[x.c]}))B++;
if(y[x.c] == min({y[x.a],y[x.b],y[x.c]}))C++;
}
A = max({A,B,C});
if(A <= bes){
bes = A;
que = x;
}
}
else if(x.t == 2){
int A = 0, B = 0, C = 0;
for(auto y : curperm){
if(y[x.a] == med(y[x.a],y[x.b],y[x.c]))A++;
if(y[x.b] == med(y[x.a],y[x.b],y[x.c]))B++;
if(y[x.c] == med(y[x.a],y[x.b],y[x.c]))C++;
}
A = max({A,B,C});
if(A <= bes){
bes = A;
que = x;
}
}
else if(x.t == 3){
int A = 0, B = 0, C = 0;
for(auto y : curperm){
if(y[x.a] == nxl(y[x.a],y[x.b],y[x.c],y[x.d]))A++;
if(y[x.b] == nxl(y[x.a],y[x.b],y[x.c],y[x.d]))B++;
if(y[x.c] == nxl(y[x.a],y[x.b],y[x.c],y[x.d]))C++;
}
A = max({A,B,C});
if(A <= bes){
bes = A;
que = x;
}
}
}
vector<vector<int>> nP;
if(que.t == 0){
int k = getHeaviest(que.a+1,que.b+1,que.c+1)-1;
for(auto y : curperm){
if(y[k] == max({y[que.a],y[que.b],y[que.c]}))nP.push_back(y);
}
}
else if(que.t == 1){
int k = getLightest(que.a+1,que.b+1,que.c+1)-1;
for(auto y : curperm){
if(y[k] == min({y[que.a],y[que.b],y[que.c]}))nP.push_back(y);
}
}
else if(que.t == 2){
int k = getMedian(que.a+1,que.b+1,que.c+1)-1;
for(auto y : curperm){
if(y[k] == med(y[que.a],y[que.b],y[que.c]))nP.push_back(y);
}
}
else if(que.t == 3){
int k = getNextLightest(que.a+1,que.b+1,que.c+1,que.d+1) - 1;
for(auto y : curperm){
if(y[k] == nxl(y[que.a],y[que.b],y[que.c],y[que.d]))nP.push_back(y);
}
}
swap(nP,curperm);
}
/* ... */
int w[6];
for(int i = 0; i < 6; ++i){
w[curperm[0][i]] = i+1;
}
answer(w);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
412 ms |
384 KB |
Output is correct |
2 |
Correct |
431 ms |
388 KB |
Output is correct |
3 |
Correct |
409 ms |
380 KB |
Output is correct |
4 |
Correct |
435 ms |
384 KB |
Output is correct |
5 |
Correct |
399 ms |
384 KB |
Output is correct |
6 |
Correct |
436 ms |
504 KB |
Output is correct |
7 |
Correct |
430 ms |
340 KB |
Output is correct |
8 |
Correct |
408 ms |
384 KB |
Output is correct |
9 |
Correct |
428 ms |
388 KB |
Output is correct |
10 |
Correct |
476 ms |
384 KB |
Output is correct |
11 |
Correct |
423 ms |
380 KB |
Output is correct |
12 |
Correct |
415 ms |
388 KB |
Output is correct |
13 |
Correct |
419 ms |
384 KB |
Output is correct |
14 |
Correct |
421 ms |
388 KB |
Output is correct |
15 |
Correct |
418 ms |
380 KB |
Output is correct |
16 |
Correct |
430 ms |
380 KB |
Output is correct |
17 |
Correct |
426 ms |
388 KB |
Output is correct |
18 |
Correct |
451 ms |
384 KB |
Output is correct |
19 |
Correct |
428 ms |
384 KB |
Output is correct |
20 |
Correct |
407 ms |
396 KB |
Output is correct |
21 |
Correct |
432 ms |
384 KB |
Output is correct |
22 |
Correct |
401 ms |
340 KB |
Output is correct |
23 |
Correct |
415 ms |
388 KB |
Output is correct |
24 |
Correct |
408 ms |
384 KB |
Output is correct |
25 |
Correct |
429 ms |
468 KB |
Output is correct |
26 |
Correct |
404 ms |
388 KB |
Output is correct |
27 |
Correct |
498 ms |
384 KB |
Output is correct |
28 |
Correct |
420 ms |
388 KB |
Output is correct |
29 |
Correct |
432 ms |
404 KB |
Output is correct |
30 |
Correct |
411 ms |
384 KB |
Output is correct |
31 |
Correct |
472 ms |
464 KB |
Output is correct |
32 |
Correct |
422 ms |
384 KB |
Output is correct |
33 |
Correct |
439 ms |
460 KB |
Output is correct |
34 |
Correct |
411 ms |
380 KB |
Output is correct |
35 |
Correct |
420 ms |
340 KB |
Output is correct |
36 |
Correct |
420 ms |
512 KB |
Output is correct |
37 |
Correct |
467 ms |
384 KB |
Output is correct |
38 |
Correct |
408 ms |
476 KB |
Output is correct |
39 |
Correct |
409 ms |
384 KB |
Output is correct |
40 |
Correct |
450 ms |
380 KB |
Output is correct |