Submission #384188

#	Time	Username	Problem	Language	Result	Execution time	Memory
384188		doowey	Scales (IOI15_scales)	C++14	75 / 100	66 ms	768 KiB

scales

#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 (stderr)

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) {
      |           ~~~~^

• Subtask 1: 75 / 100