| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 384188 |
2021-03-31T17:14:47 Z |
doowey |
Scales (IOI15_scales) |
C++14 |
|
66 ms |
768 KB |
#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
vector<vector<int>> perm;
const int M = 10000;
vector<int> nds[M];
int typ[M];
int ai[M];
int bi[M];
int ci[M];
int dd[M];
int na[M];
int nb[M];
int nc[M];
int cha;
int cnt;
int construct_tree(vector<int> inds, int dept){
if(inds.size() == 0) return -1;
cha = max(cha, dept);
int node = cnt;
cnt ++ ;
nds[node] = inds;
if(inds.size() == 1) return node;
int cdiff = (int)1e9;
vector<int> ba, bb, bc;
int aq;
int id;
for(int i = 1; i <= 6; i ++ ){
for(int j = i + 1; j <= 6; j ++ ){
for(int k = j + 1; k <= 6; k ++ ){
vector<int> sa, sb, sc;
for(auto x : inds){
vector<pii> ord;
ord.push_back(mp(perm[x][i - 1], i));
ord.push_back(mp(perm[x][j - 1], j));
ord.push_back(mp(perm[x][k - 1], k));
sort(ord.begin(), ord.end());
if(ord[0].se == i){
sa.push_back(x);
}
else if(ord[0].se == j){
sb.push_back(x);
}
else{
sc.push_back(x);
}
}
aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
if(aq < cdiff){
cdiff = aq;
ba = sa;
bb = sb;
bc = sc;
typ[node] = 1;
ai[node] = i;
bi[node] = j;
ci[node] = k;
}
sa.clear();
sb.clear();
sc.clear();
//
for(auto x : inds){
vector<pii> ord;
ord.push_back(mp(perm[x][i - 1], i));
ord.push_back(mp(perm[x][j - 1], j));
ord.push_back(mp(perm[x][k - 1], k));
sort(ord.begin(), ord.end());
if(ord[1].se == i){
sa.push_back(x);
}
else if(ord[1].se == j){
sb.push_back(x);
}
else{
sc.push_back(x);
}
}
aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
if(aq < cdiff){
cdiff = aq;
ba = sa;
bb = sb;
bc = sc;
typ[node] = 2;
ai[node] = i;
bi[node] = j;
ci[node] = k;
}
sa.clear();
sb.clear();
sc.clear();
//
for(auto x : inds){
vector<pii> ord;
ord.push_back(mp(perm[x][i - 1], i));
ord.push_back(mp(perm[x][j - 1], j));
ord.push_back(mp(perm[x][k - 1], k));
sort(ord.begin(), ord.end());
if(ord[2].se == i){
sa.push_back(x);
}
else if(ord[2].se == j){
sb.push_back(x);
}
else{
sc.push_back(x);
}
}
aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
if(aq < cdiff){
cdiff = aq;
ba = sa;
bb = sb;
bc = sc;
typ[node] = 3;
ai[node] = i;
bi[node] = j;
ci[node] = k;
}
sa.clear();
sb.clear();
sc.clear();
for(int q = 1; q <= 6; q ++ ){
if(q == i || q == j || q == k) continue;
for(auto x : inds){
vector<pii> ord;
ord.push_back(mp(perm[x][i - 1], i));
ord.push_back(mp(perm[x][j - 1], j));
ord.push_back(mp(perm[x][k - 1], k));
sort(ord.begin(), ord.end());
id = 0;
for(int f = 0 ; f < 3; f ++ ){
if(ord[f].fi > perm[x][q-1]){
id = f;
break;
}
}
if(ord[id].se == i){
sa.push_back(x);
}
else if(ord[id].se == j){
sb.push_back(x);
}
else{
sc.push_back(x);
}
}
aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
if(aq < cdiff){
cdiff = aq;
ba = sa;
bb = sb;
bc = sc;
typ[node] = 4;
ai[node] = i;
bi[node] = j;
ci[node] = k;
dd[node] = q;
}
sa.clear();
sb.clear();
sc.clear();
}
}
}
}
na[node] = construct_tree(ba, dept + 1);
nb[node] = construct_tree(bb, dept + 1);
nc[node] = construct_tree(bc, dept + 1);
return node;
}
void init(int T) {
vector<int> p = {1,2,3,4,5,6};
vector<int> ind;
do{
ind.push_back(perm.size());
perm.push_back(p);
}while(next_permutation(p.begin(), p.end()));
construct_tree(ind, 0);
}
void orderCoins() {
/* ... */
int node = 0;
int gv;
while(nds[node].size() > 1){
if(typ[node] == 1){
gv = getLightest(ai[node], bi[node], ci[node]);
}
else if(typ[node] == 2){
gv = getMedian(ai[node], bi[node], ci[node]);
}
else if(typ[node] == 3){
gv = getHeaviest(ai[node], bi[node], ci[node]);
}
else{
gv = getNextLightest(ai[node], bi[node], ci[node], dd[node]);
}
if(gv == ai[node]){
node = na[node];
}
else if(gv == bi[node]){
node = nb[node];
}
else{
node = nc[node];
}
}
int W[6];
for(int j = 0 ; j < 6; j ++ )
W[perm[nds[node][0]][j] - 1] = j + 1;
answer(W);
}
Compilation message
scales.cpp: In function 'int construct_tree(std::vector<int>, int)':
scales.cpp:60:61: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
60 | aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:91:61: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
91 | aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:122:61: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
122 | aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp:161:65: warning: conversion from 'long unsigned int' to 'int' may change value [-Wconversion]
161 | aq = max({sa.size(), sb.size(), sc.size()}) - min({sa.size(), sb.size(), sc.size()});
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:190:32: warning: conversion from 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} to 'std::vector<int>::value_type' {aka 'int'} may change value [-Wconversion]
190 | ind.push_back(perm.size());
| ~~~~~~~~~^~
scales.cpp:186:15: warning: unused parameter 'T' [-Wunused-parameter]
186 | void init(int T) {
| ~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
62 ms |
748 KB |
Output is partially correct |
| 2 |
Correct |
63 ms |
748 KB |
Output is correct |
| 3 |
Partially correct |
65 ms |
748 KB |
Output is partially correct |
| 4 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 5 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 6 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 7 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 8 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 9 |
Correct |
65 ms |
748 KB |
Output is correct |
| 10 |
Correct |
63 ms |
748 KB |
Output is correct |
| 11 |
Correct |
63 ms |
748 KB |
Output is correct |
| 12 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 13 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 14 |
Partially correct |
62 ms |
748 KB |
Output is partially correct |
| 15 |
Correct |
63 ms |
748 KB |
Output is correct |
| 16 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 17 |
Correct |
63 ms |
748 KB |
Output is correct |
| 18 |
Correct |
63 ms |
748 KB |
Output is correct |
| 19 |
Correct |
62 ms |
748 KB |
Output is correct |
| 20 |
Partially correct |
66 ms |
748 KB |
Output is partially correct |
| 21 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 22 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 23 |
Partially correct |
63 ms |
768 KB |
Output is partially correct |
| 24 |
Partially correct |
62 ms |
748 KB |
Output is partially correct |
| 25 |
Correct |
63 ms |
748 KB |
Output is correct |
| 26 |
Partially correct |
64 ms |
748 KB |
Output is partially correct |
| 27 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 28 |
Partially correct |
62 ms |
748 KB |
Output is partially correct |
| 29 |
Partially correct |
64 ms |
748 KB |
Output is partially correct |
| 30 |
Partially correct |
62 ms |
748 KB |
Output is partially correct |
| 31 |
Correct |
63 ms |
748 KB |
Output is correct |
| 32 |
Partially correct |
64 ms |
748 KB |
Output is partially correct |
| 33 |
Correct |
63 ms |
748 KB |
Output is correct |
| 34 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 35 |
Partially correct |
64 ms |
748 KB |
Output is partially correct |
| 36 |
Partially correct |
64 ms |
748 KB |
Output is partially correct |
| 37 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 38 |
Correct |
64 ms |
748 KB |
Output is correct |
| 39 |
Partially correct |
63 ms |
748 KB |
Output is partially correct |
| 40 |
Partially correct |
62 ms |
748 KB |
Output is partially correct |
