Submission #30994

#	Time	Username	Problem	Language	Result	Execution time	Memory
30994		kajebiii	Scales (IOI15_scales)	C++14	100 / 100	113 ms	2304 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

scales

#include "scales.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;


static void __checkQuery(int A, int B, int C, int D) {
    if (D == -1) {
        if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6)
            assert(0);
        if (A == B || B == C || A == C)
            assert(0);
    }
    else {
        if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6 || D < 1 || D > 6)
            assert(0);
        if (A == B || A == C || A == D || B == C || B == D || C == D)
            assert(0);
    }
}

int _getMedian(int A, int B, int C, vector<int> _ind) {
    __checkQuery(A, B, C, -1);

    A--; B--; C--;

    if (_ind[B] < _ind[A] && _ind[A] < _ind[C])
        return A + 1;

    if (_ind[C] < _ind[A] && _ind[A] < _ind[B])
        return A + 1;

    if (_ind[A] < _ind[B] && _ind[B] < _ind[C])
        return B + 1;

    if (_ind[C] < _ind[B] && _ind[B] < _ind[A])
        return B + 1;

    return C + 1;
}

int _getHeaviest(int A, int B, int C, vector<int> _ind) {
    __checkQuery(A, B, C, -1);    

    A--; B--; C--;

    if (_ind[A] > _ind[B] && _ind[A] > _ind[C])
        return A + 1;

    if (_ind[B] > _ind[A] && _ind[B] > _ind[C])
        return B + 1;

    return C + 1;
}

int _getLightest(int A, int B, int C, vector<int> _ind) {
    __checkQuery(A, B, C, -1);

    A--; B--; C--;

    if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
        return A + 1;
    
    if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
        return B + 1;

    return C + 1;
}

int _getNextLightest(int A, int B, int C, int D, vector<int> _ind) {
    int allLess = 1;    

    __checkQuery(A, B, C, D);

    A--; B--; C--; D--;

    if (_ind[A] > _ind[D] || _ind[B] > _ind[D] || _ind[C] > _ind[D])
        allLess = 0;

    if (allLess == 1) {
        if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
            return A + 1;
    
        if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
            return B + 1;

        return C + 1;
    }

    if (_ind[A] > _ind[D]) {
        if ((_ind[A] < _ind[B] || _ind[B] < _ind[D]) && (_ind[A] < _ind[C] || _ind[C] < _ind[D]))
            return A + 1;
    }

    if (_ind[B] > _ind[D]) {
        if ((_ind[B] < _ind[A] || _ind[A] < _ind[D]) && (_ind[B] < _ind[C] || _ind[C] < _ind[D]))
            return B + 1;
    }

    return C + 1;
}



vector<vector<int>> Candi;
vector<vector<int>> Qs;
vector<int> cntList[10];

int minV = INF;

vector<pi> His;
map<vector<pi>, int> Mp;
bool isCan(int times, vector<int> cd, bool find) {
    if(times < minV) {
        minV = times;
//        printf("%d\n", times);
    }
    int n = SZ(cd);
    int cnt = 0;
    for(int nn=n; nn > 1; nn = (nn+2) / 3, cnt++);
    if(cnt > times) return false;
    if(times == 0) {
        if(find && SZ(cd) > 0) Mp[His] = cd[0];
//        for(pi &e : His) printf("[%d %d] ", e.one, e.two); puts("");
        return true;
    }

    for(int cnt : cntList[6-times]) {
        vector<int> &v  = Qs[cnt];
        vector<int> nt[3];
        int q = v[0], a = v[1], b = v[2], c = v[3];
        int d = -1;
        if(q == 3) d = v[4];

        for(int x : cd) {
            int res = -1;
            if(q == 0) res = _getHeaviest(a, b, c, Candi[x]);
            if(q == 1) res = _getMedian(a, b, c, Candi[x]);
            if(q == 2) res = _getLightest(a, b, c, Candi[x]);
            if(q == 3) res = _getNextLightest(a, b, c, d, Candi[x]);
            for(int k=0; k<3; k++) if(res == v[k+1]) {
                nt[k].push_back(x);
                break;
            }
        }
        bool nowCan = true;
        for(int k=0; k<3; k++) {
            His.push_back(pi(cnt, k));
            bool res = isCan(times-1, nt[k], false);
            His.pop_back();

            if(!res) {
                nowCan = false;
                break;
            }
        }
        if(nowCan) {
            if(times == 6 || find == true) {
                Mp[His] = cnt;
                for(int k=0; k<3; k++) {
                    His.push_back(pi(cnt, k));
                    bool res = isCan(times-1, nt[k], true);
                    His.pop_back();
                }
            }
            return true;
        }
        cnt++;
    }
    return false;
}

void init(int T) {
cntList[0] = vector<int>({0});
cntList[1] = vector<int>({58});
cntList[2] = vector<int>({67, 69, 70, 73, 74, 75, 77, 78, 79});
cntList[3] = vector<int>({7, 10, 26, 29, 41, 44, 47, 50, 53, 56, 63, 76});
cntList[4] = vector<int>({3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 27, 28, 31, 34, 48, 49, 51, 52, 83, 84, 85, 92, 93, 94, 105, 106});
cntList[5] = vector<int>({1, 3, 4, 6, 7, 10, 12, 13, 15, 16, 19, 22, 25, 28, 31, 34, 37, 39, 40, 42, 43, 45, 46, 49, 52, 55});

    Candi.clear();
    int ch[6]; for(int i=0; i<6; i++) ch[i] = i+1;
    do{
        Candi.push_back(vector<int>());
        for(int i=0; i<6; i++) Candi.back().push_back(ch[i]);
    }while(next_permutation(ch, ch+6));
    for(int i=0; i<6; i++) ch[i] = (i >= 3);
    do{
        vector<int> list;
        for(int i=0; i<6; i++) if(ch[i]) list.push_back(i);
        for(int q=0; q<3; q++) {
            Qs.push_back(vector<int>());
            Qs.back().push_back(q);
            for(int x : list) Qs.back().push_back(x+1);
        }
    }while(next_permutation(ch, ch+6));

    for(int i=0; i<6; i++) ch[i] = (i >= 2) + (i == 5);
    do{
        vector<int> list; int d = -1;
        for(int i=0; i<6; i++) {
            if(ch[i] == 1) list.push_back(i);
            if(ch[i] == 2) d = i;
        }
        Qs.push_back(vector<int>());
        Qs.back().push_back(3);
        for(int x : list) Qs.back().push_back(x+1);
        Qs.back().push_back(d+1);
    }while(next_permutation(ch, ch+6));

//    for(vector<int> cd : Candi) {for(int x : cd) printf("%d ", x); puts("");}
//    for(vector<int> &v : Qs) {for(int x : v) printf("%d ", x); puts("");}


    vector<int> fs; for(int i=0; i<720; i++) fs.push_back(i);
    isCan(6, fs, false);
//    if(isCan(6, fs, false)) puts("YES!"); else puts("NO!");
/*
    vector<int> all[10];
    for(pair<vector<pi>, int> aa : Mp) {
        for(pi e : aa.one) printf("[%d %d] ", e.one, e.two); puts("");
        printf(": %d\n", aa.two);
        all[SZ(aa.one)].push_back(aa.two);
    }
    for(int i=0; i<6; i++) {
        sort(ALL(all[i]));
        all[i].erase(unique(ALL(all[i])), all[i].end());
        for(int x : all[i]) printf("%d ", x); puts("");
    }
*/
}

void orderCoins() {
    vector<pi> his;
    for(int i=0; i<6; i++) {
        int cnt = Mp[his];
        vector<int> &v  = Qs[cnt];
        vector<int> nt[3];
        int q = v[0], a = v[1], b = v[2], c = v[3];
        int d = -1;
        if(q == 3) d = v[4];

        int res;
        if(q == 0) res = getHeaviest(a, b, c);
        if(q == 1) res = getMedian(a, b, c);
        if(q == 2) res = getLightest(a, b, c);
        if(q == 3) res = getNextLightest(a, b, c, d);

        int ix = -1;
        for(int k=0; k<3; k++) if(res == v[k+1]) ix = k;
        his.push_back(pi(cnt, ix));
    }
    int ans = Mp[his];
    int w[6];
    for(int i=0; i<6; i++) w[Candi[ans][i]-1] = i+1;
    answer(w);
}

Compilation message (stderr)

scales.cpp: In function 'bool isCan(int, std::vector<int>, bool)':
scales.cpp:141:13: warning: declaration of 'cnt' shadows a previous local [-Wshadow]
     for(int cnt : cntList[6-times]) {
             ^
scales.cpp:132:9: note: shadowed declaration is here
     int cnt = 0;
         ^
scales.cpp:175:26: warning: unused variable 'res' [-Wunused-variable]
                     bool res = isCan(times-1, nt[k], true);
                          ^
scales.cpp: At global scope:
scales.cpp:186:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:263:32: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
         for(int k=0; k<3; k++) if(res == v[k+1]) ix = k;
                                ^

Subtask 1100 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...