# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
431851 |
2021-06-17T16:08:04 Z |
frodakcin |
Scales (IOI15_scales) |
C++11 |
|
61 ms |
324 KB |
#include "scales.h"
#include <cassert>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <cstring>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
const int MN = 6;
const int MP = 6*5*4*3*2*1;
using arr = std::array<int, MN>;
arr p[MP];
struct move
{
public:
int type, v[3], D;
int qry()
{
if(type==0)
return getLightest(v[0], v[1], v[2]);
if(type==1)
return getMedian(v[0], v[1], v[2]);
if(type==2)
return getHeaviest(v[0], v[1], v[2]);
if(type==3)
return getNextLightest(v[0], v[1], v[2], D);
assert(0);
return -1;
}
};
std::vector<move> moves;
void init(int T) {
arr a;
std::iota(a.begin(), a.end(), 1);
int ctr=0;
do
{
p[ctr++]=a;
} while (std::next_permutation(a.begin(), a.end()));
for(int i=1;i<=MN;++i)
for(int j=i+1;j<=MN;++j)
for(int k=j+1;k<=MN;++k)
{
moves.push_back({0, i, j, k, -1});
moves.push_back({1, i, j, k, -1});
moves.push_back({2, i, j, k, -1});
for(int l=1;l<=MN;++l)
if(l != i && l != j && l != k)
moves.push_back({3, i, j, k, l});
}
}
int get(const arr& a, const move& m)
{
auto cmp=[&](int u, int v) {return a[u-1]<a[v-1];};
int v[3] = {m.v[0], m.v[1], m.v[2]};
std::sort(v, v+3, cmp);
if(m.type == 3)
{
int x=m.D;
for(int i=1;i<3;++i)
if(cmp(v[i-1], x) && cmp(x, v[i]))
return v[i];
return v[0];
}
else
{
return v[m.type];
/* //-- retrieve index
for(int i=0;i<3;++i)
if(m.v[i]==v[m.type])
return i;
*/
}
assert(0);
return -1;
}
void orderCoins() {
/* ... */
int W[] = {1, 2, 3, 4, 5, 6};
std::vector<arr> ok(p, p+MP), ok2;
while(ok.size() > 1)
{
//printf("ok sz: %lu\n", ok.size());
int id=-1, best=MP+1;
for(int i=0;i<moves.size();++i)
{
int v[6]; memset(v, 0, sizeof v);
for(const auto& x:ok)
v[get(x, moves[i])-1]++;
if(ckmin(best, *std::max_element(v, v+6)))
id=i;
}
int q = moves[id].qry();
//printf("Type %d: %d %d %d [%d]: %d\n", moves[id].type, moves[id].v[0], moves[id].v[1], moves[id].v[2] ,moves[id].D, q);
for(const auto& x:ok)
if(get(x, moves[id])==q)
ok2.push_back(x);
ok2.swap(ok);
ok2.clear();
}
for(int i=0;i<6;++i)
W[ok[0][i]-1]=i+1;
answer(W);
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:37:15: warning: unused parameter 'T' [-Wunused-parameter]
37 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:93:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<move>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i=0;i<moves.size();++i)
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Partially correct |
60 ms |
204 KB |
Output is partially correct |
2 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
3 |
Partially correct |
58 ms |
312 KB |
Output is partially correct |
4 |
Partially correct |
57 ms |
204 KB |
Output is partially correct |
5 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
6 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
7 |
Partially correct |
60 ms |
308 KB |
Output is partially correct |
8 |
Partially correct |
59 ms |
308 KB |
Output is partially correct |
9 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
10 |
Partially correct |
59 ms |
204 KB |
Output is partially correct |
11 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
12 |
Partially correct |
57 ms |
284 KB |
Output is partially correct |
13 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
14 |
Partially correct |
59 ms |
204 KB |
Output is partially correct |
15 |
Partially correct |
58 ms |
320 KB |
Output is partially correct |
16 |
Partially correct |
58 ms |
308 KB |
Output is partially correct |
17 |
Correct |
61 ms |
308 KB |
Output is correct |
18 |
Partially correct |
59 ms |
204 KB |
Output is partially correct |
19 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
20 |
Partially correct |
58 ms |
308 KB |
Output is partially correct |
21 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
22 |
Partially correct |
58 ms |
316 KB |
Output is partially correct |
23 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
24 |
Correct |
59 ms |
204 KB |
Output is correct |
25 |
Partially correct |
57 ms |
204 KB |
Output is partially correct |
26 |
Partially correct |
58 ms |
308 KB |
Output is partially correct |
27 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
28 |
Partially correct |
58 ms |
324 KB |
Output is partially correct |
29 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
30 |
Partially correct |
58 ms |
304 KB |
Output is partially correct |
31 |
Partially correct |
57 ms |
308 KB |
Output is partially correct |
32 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
33 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
34 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
35 |
Partially correct |
59 ms |
324 KB |
Output is partially correct |
36 |
Partially correct |
60 ms |
308 KB |
Output is partially correct |
37 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
38 |
Partially correct |
59 ms |
308 KB |
Output is partially correct |
39 |
Partially correct |
58 ms |
204 KB |
Output is partially correct |
40 |
Partially correct |
60 ms |
204 KB |
Output is partially correct |