| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 621407 |
2022-08-03T18:35:47 Z |
M_W |
Scales (IOI15_scales) |
C++17 |
|
118 ms |
440 KB |
#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
vector<vector<int>> all_perm;
int A = 37, B = 61, M = 9122, last = 1;
int randInt(){
last = ((last * A) + B) % M;
return last;
}
void init(int T){
vector<int> perm = {1, 2, 3, 4, 5, 6};
do{
all_perm.push_back(perm);
} while(next_permutation(perm.begin(), perm.end()));
}
bool condition(int i1, int j1, int k1, int i2, int j2, int k2, int type1, int type2, int x1, int y1, int z1, int x2, int y2, int z2){
// Check to choose 1 instead of 2
int mx1 = max({i1, j1, k1}), mx2 = max({i2, j2, k2});
int mn1 = min({i1, j1, k1}), mn2 = min({i2, j2, k2});
int sm1 = i1 + j1 + k1, sm2 = i2 + j2 + k2;
int r = randInt();
return mx1 < mx2 || (mx1 == mx2 && type1 > type2) || (mx1 == mx2 && type1 == type2 && x1 >= x2);
}
void orderCoins(){
vector<vector<int>> cases = all_perm;
while(cases.size() > 1){
array<int, 9> ask = {INT_MAX, 0, 0, 0, 0, 0, 1000, 1000, 1000};
for(int i = 1; i <= 6; i++){
for(int j = i + 1; j <= 6; j++){
for(int k = j + 1; k <= 6; k++){
int hi = 0, hj = 0, hk = 0; // heavy count (case left)
int li = 0, lj = 0, lk = 0; // light count (case left)
int mi = 0, mj = 0, mk = 0; // median count (case left)
for(auto x : cases){
int ii, jj, kk;
for(int p = 0; p < 6; p++){
if(x[p] == i) ii = p;
if(x[p] == j) jj = p;
if(x[p] == k) kk = p;
}
// Case1: Getheaviest
if(max({ii, jj, kk}) == ii) hi++;
if(max({ii, jj, kk}) == jj) hj++;
if(max({ii, jj, kk}) == kk) hk++;
// Case2: Getlightest
if(min({ii, jj, kk}) == ii) li++;
if(min({ii, jj, kk}) == jj) lj++;
if(min({ii, jj, kk}) == kk) lk++;
// Case3: GetMedian
if(min({ii, jj, kk}) != ii && max({ii, jj, kk}) != ii) mi++;
if(min({ii, jj, kk}) != jj && max({ii, jj, kk}) != jj) mj++;
if(min({ii, jj, kk}) != kk && max({ii, jj, kk}) != kk) mk++;
}
if(condition(hi, hj, hk, ask[6], ask[7], ask[8], 1, ask[1], i, j, k, ask[2], ask[3], ask[4]))
ask = {max({hi, hj, hk}), 1, i, j, k, 0, hi, hj, hk};
if(condition(li, lj, lk, ask[6], ask[7], ask[8], 2, ask[1], i, j, k, ask[2], ask[3], ask[4]))
ask = {max({li, lj, lk}), 2, i, j, k, 0, li, lj, lk};
if(condition(mi, mj, mk, ask[6], ask[7], ask[8], 3, ask[1], i, j, k, ask[2], ask[3], ask[4]))
ask = {max({mi, mj, mk}), 3, i, j, k, 0, mi, mj, mk};
// Case4: GetNextLightest
for(int l = 1; l < 6; l++){
if(l == i || l == j || l == k) continue;
int si = 0, sj = 0, sk = 0;
for(auto x : cases){
int l2, upb = 10;
int ii, jj, kk;
for(int p = 0; p < 6; p++){
if(x[p] == l) ii = p;
if(x[p] == j) jj = p;
if(x[p] == k) kk = p;
if(x[p] == i) l2 = p;
}
vector<int> tmp = {ii, jj, kk};
for(auto y : tmp){
if(y > l2) upb = min(upb, y);
}
if(upb == 10) upb = min({ii, jj, kk});
if(ii == upb) si++;
if(jj == upb) sj++;
if(kk == upb) sk++;
}
if(condition(si, sj, sk, ask[6], ask[7], ask[8], 4, ask[1], i, j, k, ask[2], ask[3], ask[4]))
ask = {max({si, sj, sk}), 4, l, j, k, i, si, sj, sk};
}
}
}
}
int res;
vector<vector<int>> tmp = cases; cases.clear();
if(ask[1] == 1){
res = getHeaviest(ask[2], ask[3], ask[4]);
for(auto x : tmp){
int ii, jj, kk, rr;
for(int p = 0; p < 6; p++){
if(x[p] == ask[4]) ii = p;
if(x[p] == ask[2]) jj = p;
if(x[p] == ask[3]) kk = p;
if(x[p] == res) rr = p;
}
if(max({ii, jj, kk}) == rr) cases.push_back(x);
}
}
else if(ask[1] == 2){
res = getLightest(ask[4], ask[2], ask[3]);
for(auto x : tmp){
int ii, jj, kk, rr;
for(int p = 0; p < 6; p++){
if(x[p] == ask[4]) ii = p;
if(x[p] == ask[2]) jj = p;
if(x[p] == ask[3]) kk = p;
if(x[p] == res) rr = p;
}
if(min({ii, jj, kk}) == rr) cases.push_back(x);
}
}
else if(ask[1] == 3){
res = getMedian(ask[4], ask[2], ask[3]);
for(auto x : tmp){
int ii, jj, kk, rr;
for(int p = 0; p < 6; p++){
if(x[p] == ask[4]) ii = p;
if(x[p] == ask[2]) jj = p;
if(x[p] == ask[3]) kk = p;
if(x[p] == res) rr = p;
}
if(min({ii, jj, kk}) != rr && max({ii, jj, kk}) != rr) cases.push_back(x);
}
}
else{
res = getNextLightest(ask[2], ask[3], ask[4], ask[5]);
for(auto x : tmp){
int l2, upb = 10;
int ii, jj, kk, rr;
for(int p = 0; p < 6; p++){
if(x[p] == ask[2]) ii = p;
if(x[p] == ask[3]) jj = p;
if(x[p] == ask[4]) kk = p;
if(x[p] == ask[5]) l2 = p;
if(x[p] == res) rr = p;
}
vector<int> tmp = {ii, jj, kk};
for(auto y : tmp){
if(y > l2) upb = min(upb, y);
}
if(upb == 10) upb = min({ii, jj, kk});
if(upb == rr) cases.push_back(x);
}
}
}
int ans[] = {cases[0][0], cases[0][1], cases[0][2], cases[0][3], cases[0][4], cases[0][5]};
answer(ans);
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:12:15: warning: unused parameter 'T' [-Wunused-parameter]
12 | void init(int T){
| ~~~~^
scales.cpp: In function 'bool condition(int, int, int, int, int, int, int, int, int, int, int, int, int, int)':
scales.cpp:22:6: warning: unused variable 'mn1' [-Wunused-variable]
22 | int mn1 = min({i1, j1, k1}), mn2 = min({i2, j2, k2});
| ^~~
scales.cpp:22:31: warning: unused variable 'mn2' [-Wunused-variable]
22 | int mn1 = min({i1, j1, k1}), mn2 = min({i2, j2, k2});
| ^~~
scales.cpp:23:6: warning: unused variable 'sm1' [-Wunused-variable]
23 | int sm1 = i1 + j1 + k1, sm2 = i2 + j2 + k2;
| ^~~
scales.cpp:23:26: warning: unused variable 'sm2' [-Wunused-variable]
23 | int sm1 = i1 + j1 + k1, sm2 = i2 + j2 + k2;
| ^~~
scales.cpp:25:6: warning: unused variable 'r' [-Wunused-variable]
25 | int r = randInt();
| ^
scales.cpp:19:98: warning: unused parameter 'y1' [-Wunused-parameter]
19 | bool condition(int i1, int j1, int k1, int i2, int j2, int k2, int type1, int type2, int x1, int y1, int z1, int x2, int y2, int z2){
| ~~~~^~
scales.cpp:19:106: warning: unused parameter 'z1' [-Wunused-parameter]
19 | bool condition(int i1, int j1, int k1, int i2, int j2, int k2, int type1, int type2, int x1, int y1, int z1, int x2, int y2, int z2){
| ~~~~^~
scales.cpp:19:122: warning: unused parameter 'y2' [-Wunused-parameter]
19 | bool condition(int i1, int j1, int k1, int i2, int j2, int k2, int type1, int type2, int x1, int y1, int z1, int x2, int y2, int z2){
| ~~~~^~
scales.cpp:19:130: warning: unused parameter 'z2' [-Wunused-parameter]
19 | bool condition(int i1, int j1, int k1, int i2, int j2, int k2, int type1, int type2, int x1, int y1, int z1, int x2, int y2, int z2){
| ~~~~^~
scales.cpp: In function 'void orderCoins()':
scales.cpp:153:17: warning: declaration of 'tmp' shadows a previous local [-Wshadow]
153 | vector<int> tmp = {ii, jj, kk};
| ^~~
scales.cpp:101:23: note: shadowed declaration is here
101 | vector<vector<int>> tmp = cases; cases.clear();
| ^~~
scales.cpp:158:5: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
158 | if(upb == rr) cases.push_back(x);
| ^~
scales.cpp:145:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
145 | int ii, jj, kk, rr;
| ^~
scales.cpp:145:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
145 | int ii, jj, kk, rr;
| ^~
scales.cpp:145:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
145 | int ii, jj, kk, rr;
| ^~
scales.cpp:155:6: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
155 | if(y > l2) upb = min(upb, y);
| ^~
scales.cpp:138:32: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
138 | if(min({ii, jj, kk}) != rr && max({ii, jj, kk}) != rr) cases.push_back(x);
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:131:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
131 | int ii, jj, kk, rr;
| ^~
scales.cpp:131:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
131 | int ii, jj, kk, rr;
| ^~
scales.cpp:131:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
131 | int ii, jj, kk, rr;
| ^~
scales.cpp:125:5: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
125 | if(min({ii, jj, kk}) == rr) cases.push_back(x);
| ^~
scales.cpp:118:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
118 | int ii, jj, kk, rr;
| ^~
scales.cpp:118:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
118 | int ii, jj, kk, rr;
| ^~
scales.cpp:118:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
118 | int ii, jj, kk, rr;
| ^~
scales.cpp:112:5: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
112 | if(max({ii, jj, kk}) == rr) cases.push_back(x);
| ^~
scales.cpp:105:17: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
105 | int ii, jj, kk, rr;
| ^~
scales.cpp:105:13: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
105 | int ii, jj, kk, rr;
| ^~
scales.cpp:105:9: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
105 | int ii, jj, kk, rr;
| ^~
scales.cpp:76:20: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | int ii, jj, kk;
| ^~
scales.cpp:76:16: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | int ii, jj, kk;
| ^~
scales.cpp:76:12: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | int ii, jj, kk;
| ^~
scales.cpp:85:9: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
85 | if(y > l2) upb = min(upb, y);
| ^~
scales.cpp:59:34: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | if(min({ii, jj, kk}) != kk && max({ii, jj, kk}) != kk) mk++;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:58:34: warning: 'jj' may be used uninitialized in this function [-Wmaybe-uninitialized]
58 | if(min({ii, jj, kk}) != jj && max({ii, jj, kk}) != jj) mj++;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:57:34: warning: 'ii' may be used uninitialized in this function [-Wmaybe-uninitialized]
57 | if(min({ii, jj, kk}) != ii && max({ii, jj, kk}) != ii) mi++;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
94 ms |
408 KB |
Output is partially correct |
| 2 |
Correct |
89 ms |
408 KB |
Output is correct |
| 3 |
Partially correct |
86 ms |
416 KB |
Output is partially correct |
| 4 |
Correct |
85 ms |
408 KB |
Output is correct |
| 5 |
Correct |
78 ms |
412 KB |
Output is correct |
| 6 |
Correct |
89 ms |
420 KB |
Output is correct |
| 7 |
Partially correct |
88 ms |
416 KB |
Output is partially correct |
| 8 |
Partially correct |
99 ms |
416 KB |
Output is partially correct |
| 9 |
Partially correct |
83 ms |
412 KB |
Output is partially correct |
| 10 |
Correct |
94 ms |
404 KB |
Output is correct |
| 11 |
Partially correct |
93 ms |
440 KB |
Output is partially correct |
| 12 |
Partially correct |
79 ms |
412 KB |
Output is partially correct |
| 13 |
Partially correct |
109 ms |
408 KB |
Output is partially correct |
| 14 |
Partially correct |
89 ms |
340 KB |
Output is partially correct |
| 15 |
Partially correct |
97 ms |
412 KB |
Output is partially correct |
| 16 |
Partially correct |
107 ms |
408 KB |
Output is partially correct |
| 17 |
Correct |
78 ms |
408 KB |
Output is correct |
| 18 |
Partially correct |
92 ms |
340 KB |
Output is partially correct |
| 19 |
Partially correct |
100 ms |
412 KB |
Output is partially correct |
| 20 |
Partially correct |
97 ms |
412 KB |
Output is partially correct |
| 21 |
Partially correct |
78 ms |
404 KB |
Output is partially correct |
| 22 |
Partially correct |
86 ms |
300 KB |
Output is partially correct |
| 23 |
Partially correct |
86 ms |
340 KB |
Output is partially correct |
| 24 |
Partially correct |
103 ms |
404 KB |
Output is partially correct |
| 25 |
Partially correct |
81 ms |
412 KB |
Output is partially correct |
| 26 |
Partially correct |
85 ms |
424 KB |
Output is partially correct |
| 27 |
Partially correct |
77 ms |
340 KB |
Output is partially correct |
| 28 |
Partially correct |
89 ms |
408 KB |
Output is partially correct |
| 29 |
Partially correct |
80 ms |
412 KB |
Output is partially correct |
| 30 |
Partially correct |
77 ms |
412 KB |
Output is partially correct |
| 31 |
Partially correct |
82 ms |
404 KB |
Output is partially correct |
| 32 |
Partially correct |
86 ms |
404 KB |
Output is partially correct |
| 33 |
Partially correct |
118 ms |
416 KB |
Output is partially correct |
| 34 |
Correct |
87 ms |
412 KB |
Output is correct |
| 35 |
Partially correct |
80 ms |
300 KB |
Output is partially correct |
| 36 |
Correct |
75 ms |
408 KB |
Output is correct |
| 37 |
Correct |
82 ms |
408 KB |
Output is correct |
| 38 |
Partially correct |
95 ms |
412 KB |
Output is partially correct |
| 39 |
Partially correct |
85 ms |
340 KB |
Output is partially correct |
| 40 |
Partially correct |
80 ms |
428 KB |
Output is partially correct |
