Submission #768392

#	Time	Username	Problem	Language	Result	Execution time	Memory
768392		boyliguanhan	Scales (IOI15_scales)	C++17	100 / 100	70 ms	832 KiB

scales

#include "scales.h"
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
int limit[6] {243,81,27,9,3,1};
int check(vector<int> perm, int a, int b, int c, int d, int op) {
    vector<int> v;
    int cnt = 0, x = 1;
    for(auto i: perm)
        if(i==a||i==b||i==c) {
            if(x) v.push_back(i), x = 0;
            if(++cnt==op)
                return i;
        } else if(i==d) {
            x = 1;
        }
    return v.back();
}
inline int get(int a,int b, int c, int d, int op) {
    switch(op) {
        case 1: return getLightest(a,b,c);
        case 2: return getMedian(a,b,c);
        case 3: return getHeaviest(a,b,c);
        default: return getNextLightest(a,b,c,d);
    }
}
map<vector<vector<int>>, vector<int>> which;
bool ok(vector<vector<int>> poss, int x = 0) {
    if(poss.size()<2) return 1;
    for(int i = 1; i < 5; i++)
        for(int j = i+1; j < 6; j++)
            for(int k = j+1; k < 7; k++)
                for(int op = 5; --op;) {
                    for(int d = 7; d--;) {
                        if(d==i||d==j||d==k) continue;
                        if(!d&&op>3) continue;
                        if(d&&op<4) continue;
                        vector<vector<int>> split[7];
                        for(auto v: poss) split[check(v,i,j,k, d,op)].push_back(v);
                        int Y = 0;
                        for(auto v:split)
                            Y = max(Y, (int)v.size());
                        if(Y<=limit[x]) {
                            if(ok(split[i], x+1)&&ok(split[j],x+1)&&ok(split[k],x+1))
                                return which[poss]=(vector<int>{i,j,k,op,d}), 1;
                        }
                    }
                }
    return 0;
}
int X[6];
int* dfs(vector<vector<int>> poss, int x = 0) {
    if(poss.size()==1) {
        for(int i =0; i < 6; i++)
            X[i] = poss[0][i];
        return X;
    }
    vector<int> v = which[poss];
    int i = v[0],j = v[1],k = v[2],op = v[3],d = v[4];
    vector<vector<int>> split[7];
    for(auto v: poss) split[check(v,i,j,k, d,op)].push_back(v);
    return dfs(split[get(i,j,k,d,op)], x+1);
}
void init(int T) {
    vector<vector<int>> v;
    vector<int> x {1,2,3,4,5,6};
    do 
        v.push_back(x);
    while(next_permutation(x.begin(), x.end()));
    ok(v);
}
void orderCoins(){
    vector<vector<int>> v;
    vector<int> x {1,2,3,4,5,6};
    do 
        v.push_back(x);
    while(next_permutation(x.begin(), x.end()));
	answer(dfs(v));
}

Compilation message (stderr)

scales.cpp: In function 'int* dfs(std::vector<std::vector<int> >, int)':
scales.cpp:61:14: warning: declaration of 'v' shadows a previous local [-Wshadow]
   61 |     for(auto v: poss) split[check(v,i,j,k, d,op)].push_back(v);
      |              ^
scales.cpp:58:17: note: shadowed declaration is here
   58 |     vector<int> v = which[poss];
      |                 ^
scales.cpp: In function 'void init(int)':
scales.cpp:64:15: warning: unused parameter 'T' [-Wunused-parameter]
   64 | void init(int T) {
      |           ~~~~^

• Subtask 1: 100 / 100