| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 432816 |
2021-06-18T13:30:52 Z |
jeroenodb |
Scales (IOI15_scales) |
C++14 |
|
41 ms |
588 KB |
#ifndef GRADER
#include "scales.h"
#endif
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
typedef array<char,6> state;
vector<state> getcombs() {
vector<state> res;
for(int i=0;i<1<<6;++i) {
vector<int8_t> h, o;
for(int8_t j=0;j<6;++j) {
if((1<<j)&i)
h.push_back(j);
else o.push_back(j);
}
if(h.size()==3) res.push_back(state{h[0],h[1],h[2], o[0],o[1],o[2]});
}
return res;
}
const vector<state> combs = getcombs();
const int allowed[] = {1,3,9,27,81,243};
struct maybe{
vector<state> to[3];
bool good=true;
maybe(int8_t op, vector<state>& left, state comb, uint8_t dead=100) {
for(auto s : left) {
array<int8_t, 3> v = {s[comb[0]],s[comb[1]],s[comb[2]]};
sort(all(v));
if(op==0) {
for(int i=0;i<3;++i) if(s[comb[i]]==v[2]) to[i].push_back(s);
} else if(op==1) {
for(int i=0;i<3;++i) if(s[comb[i]]==v[0]) to[i].push_back(s);
} else if(op==2) {
for(int i=0;i<3;++i) if(s[comb[i]]==v[1]) to[i].push_back(s);
} else {
int8_t d = s[comb[op]];
int8_t want=v[0];
for(auto i: v) {
if(i>d) {
want=i;
break;
}
}
for(int i=0;i<3;++i) if(s[comb[i]]==want) to[i].push_back(s);
}
}
for(int i=0;i<3;++i) if(dead<100 and to[i].size()>allowed[dead-1]) {
good = false;
}
}
};
struct res {
bool good;
int8_t op, comb;
};
map<vector<state>,res> dp;
res solve(vector<state>& left, int d = 6) {
if(left.size()<=1) return {true,{}};
auto it = dp.find(left);
if(it!=dp.end()) return it->second;
// try each operation
for(int8_t i=0;i<combs.size();++i) {
// try each op
for(int8_t op=0;op<6;++op) {
maybe m(op,left,combs[i],d);
if(m.good) {
for(int i=0;i<3;++i) {
auto r = solve(m.to[i],d-1);
if(!r.good) {
m.good=false;
break;
}
}
if(m.good) {
return dp[left] = {true,op,i};
}
}
}
}
return dp[left] = {false,-1,-1};
}
vector<state> allperms() {
state s;
iota(all(s),0);
vector<state> complete;
do {
complete.push_back(s);
} while(next_permutation(all(s)));
return complete;
}
void init(int T) {
}
void orderCoins() {
auto s = allperms();
while(s.size()>1) {
auto ans = solve(s);
assert(ans.good);
auto myc = combs[ans.comb];
auto partition = maybe(ans.op,s,myc);
int q;
int A=myc[0]+1,B=myc[1]+1,C=myc[2]+1,D=myc[ans.op]+1;
if(ans.op==0) {
q=getHeaviest(A,B,C);
} else if(ans.op==1) {
q=getLightest(A,B,C);
} else if(ans.op==2) {
q=getMedian(A,B,C);
} else {
q=getNextLightest(A,B,C,D);
}
q--;
for(int i=0;i<3;++i) {
if(myc[i]==q) {
s= partition.to[i];
break;
}
}
}
int order[6];
for(int i=0;i<6;++i) {
order[s[0][i]]=i+1;
}
answer(order);
}
Compilation message
scales.cpp: In constructor 'maybe::maybe(int8_t, std::vector<std::array<char, 6> >&, state, uint8_t)':
scales.cpp:56:58: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<char, 6> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
56 | for(int i=0;i<3;++i) if(dead<100 and to[i].size()>allowed[dead-1]) {
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~
scales.cpp: In function 'res solve(std::vector<std::array<char, 6> >&, int)':
scales.cpp:68:39: warning: missing initializer for member 'res::comb' [-Wmissing-field-initializers]
68 | if(left.size()<=1) return {true,{}};
| ^
scales.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int8_t' {aka 'signed char'} and 'std::vector<std::array<char, 6> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int8_t i=0;i<combs.size();++i) {
| ~^~~~~~~~~~~~~
scales.cpp:75:38: warning: conversion from 'int' to 'uint8_t' {aka 'unsigned char'} may change value [-Wconversion]
75 | maybe m(op,left,combs[i],d);
| ^
scales.cpp:77:25: warning: declaration of 'i' shadows a previous local [-Wshadow]
77 | for(int i=0;i<3;++i) {
| ^
scales.cpp:72:16: note: shadowed declaration is here
72 | for(int8_t i=0;i<combs.size();++i) {
| ^
scales.cpp: In function 'void init(int)':
scales.cpp:101:15: warning: unused parameter 'T' [-Wunused-parameter]
101 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:132:22: warning: array subscript has type 'char' [-Wchar-subscripts]
132 | order[s[0][i]]=i+1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
468 KB |
Output is correct |
| 2 |
Correct |
33 ms |
324 KB |
Output is correct |
| 3 |
Correct |
35 ms |
412 KB |
Output is correct |
| 4 |
Correct |
33 ms |
360 KB |
Output is correct |
| 5 |
Correct |
35 ms |
332 KB |
Output is correct |
| 6 |
Correct |
34 ms |
332 KB |
Output is correct |
| 7 |
Correct |
33 ms |
336 KB |
Output is correct |
| 8 |
Correct |
35 ms |
456 KB |
Output is correct |
| 9 |
Correct |
34 ms |
352 KB |
Output is correct |
| 10 |
Correct |
34 ms |
332 KB |
Output is correct |
| 11 |
Correct |
35 ms |
392 KB |
Output is correct |
| 12 |
Correct |
36 ms |
356 KB |
Output is correct |
| 13 |
Correct |
34 ms |
332 KB |
Output is correct |
| 14 |
Correct |
41 ms |
332 KB |
Output is correct |
| 15 |
Correct |
34 ms |
384 KB |
Output is correct |
| 16 |
Correct |
33 ms |
480 KB |
Output is correct |
| 17 |
Correct |
33 ms |
332 KB |
Output is correct |
| 18 |
Correct |
35 ms |
448 KB |
Output is correct |
| 19 |
Correct |
34 ms |
588 KB |
Output is correct |
| 20 |
Correct |
40 ms |
344 KB |
Output is correct |
| 21 |
Correct |
34 ms |
332 KB |
Output is correct |
| 22 |
Correct |
35 ms |
320 KB |
Output is correct |
| 23 |
Correct |
34 ms |
320 KB |
Output is correct |
| 24 |
Correct |
33 ms |
348 KB |
Output is correct |
| 25 |
Correct |
33 ms |
360 KB |
Output is correct |
| 26 |
Correct |
35 ms |
360 KB |
Output is correct |
| 27 |
Correct |
37 ms |
344 KB |
Output is correct |
| 28 |
Correct |
33 ms |
452 KB |
Output is correct |
| 29 |
Correct |
34 ms |
324 KB |
Output is correct |
| 30 |
Correct |
33 ms |
416 KB |
Output is correct |
| 31 |
Correct |
33 ms |
348 KB |
Output is correct |
| 32 |
Correct |
33 ms |
336 KB |
Output is correct |
| 33 |
Correct |
34 ms |
336 KB |
Output is correct |
| 34 |
Correct |
33 ms |
396 KB |
Output is correct |
| 35 |
Correct |
34 ms |
352 KB |
Output is correct |
| 36 |
Correct |
34 ms |
340 KB |
Output is correct |
| 37 |
Correct |
32 ms |
360 KB |
Output is correct |
| 38 |
Correct |
33 ms |
332 KB |
Output is correct |
| 39 |
Correct |
34 ms |
408 KB |
Output is correct |
| 40 |
Correct |
33 ms |
368 KB |
Output is correct |
