Submission #130568

#	Time	Username	Problem	Language	Result	Execution time	Memory
130568		keko37	Scales (IOI15_scales)	C++14	100 / 100	10 ms	512 KiB

scales

#include <bits/stdc++.h>
#include "scales.h"
 
using namespace std;
 
const int MAXN = 5005;
 
int cnt, kreni;
int sus[3][MAXN];
int p[750][7], pos[750][7];
int sol[MAXN], tip[MAXN], aa[MAXN], bb[MAXN], cc[MAXN], dd[MAXN];
 
void indeksiraj () {
    int c[6] = {0, 1, 2, 3, 4, 5};
    int cnt = 0;
    do {
        for (int i=0; i<6; i++) {
            p[cnt][i] = c[i];
            pos[cnt][p[cnt][i]] = i;
        }
        cnt++;
    } while (next_permutation(c, c + 6));
}
 
vector <int> va, vb, vc;
 
bool partMin (const vector <int> &v, int a, int b, int c, int siz) {
    va.clear(); vb.clear(); vc.clear();
    int lim = v.size(), x, y, z;
    for (int i=0; i<lim; i++) {
        x = pos[v[i]][a];
        y = pos[v[i]][b];
        z = pos[v[i]][c];
        if (x < y && x < z) va.push_back(v[i]);
        if (y < x && y < z) vb.push_back(v[i]);
        if (z < x && z < y) vc.push_back(v[i]);
        if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
    }
    return 1;
}
 
bool partMax (const vector <int> &v, int a, int b, int c, int siz) {
    va.clear(); vb.clear(); vc.clear();
    int lim = v.size(), x, y, z;
    for (int i=0; i<lim; i++) {
        x = pos[v[i]][a];
        y = pos[v[i]][b];
        z = pos[v[i]][c];
        if (x > y && x > z) va.push_back(v[i]);
        if (y > x && y > z) vb.push_back(v[i]);
        if (z > x && z > y) vc.push_back(v[i]);
        if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
    }
    return 1;
}
 
bool partMed (const vector <int> &v, int a, int b, int c, int siz) {
    va.clear(); vb.clear(); vc.clear();
    int lim = v.size(), x, y, z;
    for (int i=0; i<lim; i++) {
        x = pos[v[i]][a];
        y = pos[v[i]][b];
        z = pos[v[i]][c];
        if (y < x && x < z || z < x && x < y) va.push_back(v[i]);
        if (x < y && y < z || z < y && y < x) vb.push_back(v[i]);
        if (x < z && z < y || y < z && z < x) vc.push_back(v[i]);
        if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
    }
    return 1;
}
 
bool partMagic (const vector <int> &v, int a, int b, int c, int d, int siz) {
    va.clear(); vb.clear(); vc.clear();
    int lim = v.size(), x, y, z, w;
    for (int i=0; i<lim; i++) {
        x = pos[v[i]][a];
        y = pos[v[i]][b];
        z = pos[v[i]][c];
        w = pos[v[i]][d];
        if (x < y && y < z) {
            if (w < x) va.push_back(v[i]);
            else if (w < y) vb.push_back(v[i]);
            else if (w < z) vc.push_back(v[i]);
            else va.push_back(v[i]);
        } else if (x < z && z < y) {
            if (w < x) va.push_back(v[i]);
            else if (w < z) vc.push_back(v[i]);
            else if (w < y) vb.push_back(v[i]);
            else va.push_back(v[i]);
        } else if (y < x && x < z) {
            if (w < y) vb.push_back(v[i]);
            else if (w < x) va.push_back(v[i]);
            else if (w < z) vc.push_back(v[i]);
            else vb.push_back(v[i]);
        } else if (y < z && z < x) {
            if (w < y) vb.push_back(v[i]);
            else if (w < z) vc.push_back(v[i]);
            else if (w < x) va.push_back(v[i]);
            else vb.push_back(v[i]);
        } else if (z < x && x < y) {
            if (w < z) vc.push_back(v[i]);
            else if (w < x) va.push_back(v[i]);
            else if (w < y) vb.push_back(v[i]);
            else vc.push_back(v[i]);
        } else if (z < y && y < x) {
            if (w < z) vc.push_back(v[i]);
            else if (w < y) vb.push_back(v[i]);
            else if (w < x) va.push_back(v[i]);
            else vc.push_back(v[i]);
        }
        if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
    }
    return 1;
}
 
bool ima (vector <int> v, int x) {
    for (auto e : v) if (e == x) return 1; return 0;
}
 
int nadi (vector <int> v, int siz, int dub) {
    if (v.size() <= 1) {
        cnt++;
        //if (cnt == 1668) cout << "sad je " << v[0] << endl;
        if (!v.empty()) sol[cnt] = v[0] + 1;
        return cnt;
    }
    for (int a=0; a<6; a++) {
        for (int b=a+1; b<6; b++) {
            for (int c=b+1; c<6; c++) {
                if (partMin(v, a, b, c, siz/3)) {
                    vector <int> vva = va, vvb = vb, vvc = vc;
                    int sa, sb, sc, flg = 0;
                    if (flg == 0) {sa = nadi(vva, siz/3, dub + 1); if (sa == 0) flg = 1;}
                    if (flg == 0) {sb = nadi(vvb, siz/3, dub + 1); if (sb == 0) flg = 1;}
                    if (flg == 0) {sc = nadi(vvc, siz/3, dub + 1); if (sc == 0) flg = 1;}
                    if (flg == 0) {
                        cnt++;
                        tip[cnt] = 1; aa[cnt] = a; bb[cnt] = b; cc[cnt] = c;
                        sus[0][cnt] = sa; sus[1][cnt] = sb; sus[2][cnt] = sc;
                        return cnt;
                    }
                }
                if (partMax(v, a, b, c, siz/3)) {
                    vector <int> vva = va, vvb = vb, vvc = vc;
                    int sa, sb, sc, flg = 0;
                    if (flg == 0) {sa = nadi(vva, siz/3, dub + 1); if (sa == 0) flg = 1;}
                    if (flg == 0) {sb = nadi(vvb, siz/3, dub + 1); if (sb == 0) flg = 1;}
                    if (flg == 0) {sc = nadi(vvc, siz/3, dub + 1); if (sc == 0) flg = 1;}
                    if (flg == 0) {
                        cnt++;
                        tip[cnt] = 2; aa[cnt] = a; bb[cnt] = b; cc[cnt] = c;
                        sus[0][cnt] = sa; sus[1][cnt] = sb; sus[2][cnt] = sc;
                        return cnt;
                    }
                }
                if (partMed(v, a, b, c, siz/3)) {
                    vector <int> vva = va, vvb = vb, vvc = vc;
                    int sa, sb, sc, flg = 0;
                    if (flg == 0) {sa = nadi(vva, siz/3, dub + 1); if (sa == 0) flg = 1;}
                    if (flg == 0) {sb = nadi(vvb, siz/3, dub + 1); if (sb == 0) flg = 1;}
                    if (flg == 0) {sc = nadi(vvc, siz/3, dub + 1); if (sc == 0) flg = 1;}
                    if (flg == 0) {
                        cnt++;
                        //if (cnt == 1670) cout << "bla " << vva[0] << " " << vvb[0] << " " << vvc[0] << "  " << ima(v, 719) << endl;
                        tip[cnt] = 3; aa[cnt] = a; bb[cnt] = b; cc[cnt] = c;
                        sus[0][cnt] = sa; sus[1][cnt] = sb; sus[2][cnt] = sc;
                        return cnt;
                    }
                }
                for (int d = 0; d < 6; d++) {
                    if (d == a || d == b || d == c) continue;
                    if (partMagic(v, a, b, c, d, siz/3)) {
                        vector <int> vva = va, vvb = vb, vvc = vc;
                        int sa, sb, sc, flg = 0;
                        if (flg == 0) {sa = nadi(vva, siz/3, dub + 1); if (sa == 0) flg = 1;}
                        if (flg == 0) {sb = nadi(vvb, siz/3, dub + 1); if (sb == 0) flg = 1;}
                        if (flg == 0) {sc = nadi(vvc, siz/3, dub + 1); if (sc == 0) flg = 1;}
                        if (flg == 0) {
                            cnt++;
                            tip[cnt] = 4; aa[cnt] = a; bb[cnt] = b; cc[cnt] = c; dd[cnt] = d;
                            sus[0][cnt] = sa; sus[1][cnt] = sb; sus[2][cnt] = sc;
                            return cnt;
                        }
                    }
                }
            }
        }
    }
    return 0;
}
 
void init (int T) {
    indeksiraj();
    vector <int> v;
    for (int i=0; i<720; i++) v.push_back(i);
    kreni = nadi(v, 729, 0);
}
 
/*
void answer(int A[]) {}
int getLightest (int a, int b, int c) {cout << "L " << a << " " << b << " " << c << endl; int res; cin >> res; return res;}
int getHeaviest (int a, int b, int c) {cout << "H " << a << " " << b << " " << c << endl; int res; cin >> res; return res;}
int getMedian (int a, int b, int c) {cout << "M " << a << " " << b << " " << c << endl; int res; cin >> res; return res;}
int getNextLightest (int a, int b, int c, int d) {cout << "NL " << a << " " << b << " " << c << " " << d << endl; int res; cin >> res; return res;}
*/
 
int rjesi (int curr) {
    if (sol[curr] != 0) return sol[curr] - 1;
    int a = aa[curr] + 1, b = bb[curr] + 1, c = cc[curr] + 1, d = dd[curr] + 1;
    int res;
    if (tip[curr] == 1) res = getLightest(a, b, c);
    if (tip[curr] == 2) res = getHeaviest(a, b, c);
    if (tip[curr] == 3) res = getMedian(a, b, c);
    if (tip[curr] == 4) res = getNextLightest(a, b, c, d);
    if (res == a) return rjesi(sus[0][curr]);
    if (res == b) return rjesi(sus[1][curr]);
    if (res == c) return rjesi(sus[2][curr]);
}
 
void orderCoins() {
    int ind = rjesi(kreni);
    //for (int i=0; i<6; i++) cout << p[ind][i] + 1 << " "; cout << endl;
    int A[] = {p[ind][0] + 1, p[ind][1] + 1, p[ind][2] + 1, p[ind][3] + 1, p[ind][4] + 1, p[ind][5] + 1};
    answer(A);
}
 
/*int main () {
    init(1);
    for (int i=0; i<5; i++) {
        orderCoins();
    }
    return 0;
}*/

Compilation message (stderr)

scales.cpp: In function 'void indeksiraj()':
scales.cpp:15:9: warning: declaration of 'cnt' shadows a global declaration [-Wshadow]
     int cnt = 0;
         ^~~
scales.cpp:8:5: note: shadowed declaration is here
 int cnt, kreni;
     ^~~
scales.cpp: In function 'bool partMin(const std::vector<int>&, int, int, int, int)':
scales.cpp:29:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     int lim = v.size(), x, y, z;
               ~~~~~~^~
scales.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
             ~~~~~~~~~~^~~~~
scales.cpp:37:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
                                ~~~~~~~~~~^~~~~
scales.cpp:37:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
                                                   ~~~~~~~~~~^~~~~
scales.cpp: In function 'bool partMax(const std::vector<int>&, int, int, int, int)':
scales.cpp:44:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     int lim = v.size(), x, y, z;
               ~~~~~~^~
scales.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
             ~~~~~~~~~~^~~~~
scales.cpp:52:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
                                ~~~~~~~~~~^~~~~
scales.cpp:52:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
                                                   ~~~~~~~~~~^~~~~
scales.cpp: In function 'bool partMed(const std::vector<int>&, int, int, int, int)':
scales.cpp:59:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     int lim = v.size(), x, y, z;
               ~~~~~~^~
scales.cpp:64:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if (y < x && x < z || z < x && x < y) va.push_back(v[i]);
             ~~~~~~^~~~~~~~
scales.cpp:65:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if (x < y && y < z || z < y && y < x) vb.push_back(v[i]);
             ~~~~~~^~~~~~~~
scales.cpp:66:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if (x < z && z < y || y < z && z < x) vc.push_back(v[i]);
             ~~~~~~^~~~~~~~
scales.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
             ~~~~~~~~~~^~~~~
scales.cpp:67:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
                                ~~~~~~~~~~^~~~~
scales.cpp:67:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
                                                   ~~~~~~~~~~^~~~~
scales.cpp: In function 'bool partMagic(const std::vector<int>&, int, int, int, int, int)':
scales.cpp:74:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
     int lim = v.size(), x, y, z, w;
               ~~~~~~^~
scales.cpp:111:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
             ~~~~~~~~~~^~~~~
scales.cpp:111:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
                                ~~~~~~~~~~^~~~~
scales.cpp:111:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (va.size() > siz || vb.size() > siz || vc.size() > siz) return 0;
                                                   ~~~~~~~~~~^~~~~
scales.cpp: In function 'bool ima(std::vector<int>, int)':
scales.cpp:117:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (auto e : v) if (e == x) return 1; return 0;
     ^~~
scales.cpp:117:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for (auto e : v) if (e == x) return 1; return 0;
                                            ^~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:192:16: warning: unused parameter 'T' [-Wunused-parameter]
 void init (int T) {
                ^
scales.cpp: In function 'int rjesi(int)':
scales.cpp:218:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
scales.cpp:217:5: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (res == c) return rjesi(sus[2][curr]);
     ^~

• Subtask 1: 100 / 100