Submission #53928

#	Time	Username	Problem	Language	Result	Execution time	Memory
53928		Benq	Scales (IOI15_scales)	C++14	100 / 100	306 ms	1100 KiB

scales

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;


// GRADER

#include "scales.h"

/*vi VAL = {0,3,2,4,1,5,6};

void answer(int* v) {
    F0R(i,6) cout << v[i] << " ";
    cout << "\n";
}

bool CMP(int a, int b) { return VAL[a] < VAL[b]; }
int GETR(vi a, int b) { sort(all(a),CMP); return a[b]; }
int getLightest(int A, int B, int C) { return GETR({A,B,C},0); }
int getHeaviest(int A, int B, int C) { return GETR({A,B,C},2); }
int getMedian(int A, int B, int C) { return GETR({A,B,C},1); }
int getNextLightest(int A, int B, int C, int D) {
    vi z = {A,B,C}; sort(all(z),CMP);
    F0R(i,3) if (CMP(D,z[i])) return z[i];
    return z[0];
}*/

vi val(6);
vector<vi> al;

bool cmp(int a, int b) { return val[a] < val[b]; }
int getR(vi a, int b) { sort(all(a),cmp); return a[b]; }
int lightest(int A, int B, int C) { return getR({A,B,C},0); }
int heaviest(int A, int B, int C) { return getR({A,B,C},2); }
int median(int A, int B, int C) { return getR({A,B,C},1); }
int nextlightest(int A, int B, int C, int D) {
    vi z = {A,B,C}; sort(all(z),cmp);
    F0R(i,3) if (cmp(D,z[i])) return z[i];
    return z[0];
}

bool bad(bitset<720> b, int num) {
    if (pow(3,num) < b.count()) return 1;
    return 0;
}

int eval(int ind, vi v) {
    vi VAL = val;
    F0R(i,6) val[al[ind][i]] = i;
    int z = -1;
    if (v[0] == 3) z = nextlightest(v[1],v[2],v[3],v[4]);
    if (v[0] == 0) z = lightest(v[1],v[2],v[3]);
    if (v[0] == 1) z = median(v[1],v[2],v[3]);
    if (v[0] == 2) z = heaviest(v[1],v[2],v[3]);
    val = VAL;
    return z;
}

struct CMPCMP {
    bool operator()(const pair<bitset<720>,int>& l, const pair<bitset<720>,int>& r) const {
        F0R(i,720) if (l.f[i] != r.f[i]) return l.f[i] < r.f[i];
        return l.s < r.s;
    }
};

map<pair<bitset<720>,int>,bool,CMPCMP> good;

vector<bitset<720>> gen(bitset<720> b, vi v) {
    bitset<720> tmp[6];
    F0R(i,720) if (b[i]) tmp[eval(i,v)][i] = 1;
    vector<bitset<720>> ans;
    F0R(i,6) if (tmp[i].count()) ans.pb(tmp[i]);
    return ans;
}

bool guarantee(bitset<720> b, int num) {
    if (b.count() == 1) return 1;
    if (bad(b,num)) return 0;
    if (good.count({b,num})) return good[{b,num}];
    F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6) F0R(l,6) if (l != i && l != j && l != k) {
        vector<bitset<720>> v = gen(b,{3,i,j,k,l});
        bool tri = 1;
        for (auto a: v) if (bad(a,num-1)) {
            tri = 0;
            break;
        }
        if (tri) {
            for (auto a: v) if (!guarantee(a,num-1)) {
                tri = 0;
                break;
            }
            if (tri) {
                /*if (b.count() >= 80) {
                    for (auto a: v) cout << "ZZ " << b.count() << " " << a.count() << " " << good[{a,num-1}] << " " << a << "\n";
                }*/
                return good[{b,num}] = 1;
            }
        }
    }
    F0R(z,3) F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6)  {
        vector<bitset<720>> v = gen(b,{z,i,j,k});
        bool tri = 1;
        for (auto a: v) if (bad(a,num-1)) {
            tri = 0;
            break;
        }
        if (tri) {
            for (auto a: v) if (!guarantee(a,num-1)) {
                tri = 0;
                break;
            }
            if (tri) {
                return good[{b,num}] = 1;
            }
        }
    }
    return good[{b,num}] = 0;
}

void init(int T) {
    al.clear();
    vi z = {0,1,2,3,4,5};
    do {
        al.pb(z);
    } while (next_permutation(all(z)));
    
    bitset<720> x; F0R(i,720) x[i] = 1;
    guarantee(x,6);
}

void solve(bitset<720> b, int num) {
    if (b.count() == 1) {
        F0R(i,720) if (b[i]) {
            int vv[6];
            F0R(j,6) vv[j] = al[i][j]+1;
            answer(vv);
        }
        return;
    }
    if (!good.count({b,num})) {
        cout << "OOPS " << b.count() << " " << num << " " << b << "\n";
        return;
    }
    F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6) F0R(l,6) if (l != i && l != j && l != k) {
        vector<bitset<720>> v = gen(b,{3,i,j,k,l});
        
        bool tri = 1;
        for (auto a: v) if (!good.count({a,num-1}) || good[{a,num-1}] == 0) {
            tri = 0;
            break;
        }
        if (tri) {
            /*cout << "HUH " << i << " " << j << " " << k << " " << l << "\n";
            for (auto a: v) cout << a.count() << " ";
            cout << "\n";*/
            if (tri) {
                int x = getNextLightest(i+1,j+1,k+1,l+1)-1;
                bitset<720> B;
                F0R(I,720) {
                    // cout << eval(I,{0,i,j,k,l}) << "\n";
                    if (b[I] && eval(I,{3,i,j,k,l}) == x) B[I] = 1;
                }
                solve(B,num-1);
                return;
            }
        }
    }
    F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6)  {
        vector<bitset<720>> v = gen(b,{0,i,j,k});
        bool tri = 1;
        for (auto a: v) if (bad(a,num-1)) {
            tri = 0;
            break;
        }
        if (tri) {
            for (auto a: v) if (!guarantee(a,num-1)) {
                tri = 0;
                break;
            }
            if (tri) {
                int x = getLightest(i+1,j+1,k+1)-1;
                bitset<720> B;
                F0R(I,720) {
                    // cout << eval(I,{0,i,j,k,l}) << "\n";
                    if (b[I] && eval(I,{0,i,j,k}) == x) B[I] = 1;
                }
                solve(B,num-1);
                return;
            }
        }
    }
    F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6)  {
        vector<bitset<720>> v = gen(b,{1,i,j,k});
        bool tri = 1;
        for (auto a: v) if (bad(a,num-1)) {
            tri = 0;
            break;
        }
        if (tri) {
            for (auto a: v) if (!guarantee(a,num-1)) {
                tri = 0;
                break;
            }
            if (tri) {
                int x = getMedian(i+1,j+1,k+1)-1;
                bitset<720> B;
                F0R(I,720) {
                    // cout << eval(I,{0,i,j,k,l}) << "\n";
                    if (b[I] && eval(I,{1,i,j,k}) == x) B[I] = 1;
                }
                solve(B,num-1);
                return;
            }
        }
    }
    F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6)  {
        vector<bitset<720>> v = gen(b,{2,i,j,k});
        bool tri = 1;
        for (auto a: v) if (bad(a,num-1)) {
            tri = 0;
            break;
        }
        if (tri) {
            for (auto a: v) if (!guarantee(a,num-1)) {
                tri = 0;
                break;
            }
            if (tri) {
                int x = getHeaviest(i+1,j+1,k+1)-1;
                bitset<720> B;
                F0R(I,720) {
                    // cout << eval(I,{0,i,j,k,l}) << "\n";
                    if (b[I] && eval(I,{2,i,j,k}) == x) B[I] = 1;
                }
                solve(B,num-1);
                return;
            }
        }
    }
}

void orderCoins() {
    bitset<720> b; F0R(i,720) b[i] = 1;
    solve(b,6);
}

/*int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    init(1);
    orderCoins();
    orderCoins();
}*/

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS

Compilation message (stderr)

In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
     if (_ghksjhdfkae19ga_ > 1) 
     ^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  for (i = 0; i < 6; i++) {
  ^~~
scales.cpp: In function 'bool bad(std::bitset<720>, int)':
scales.cpp:81:29: warning: conversion to '__gnu_cxx::__promote_2<int, int, double, double>::__type {aka double}' from 'std::size_t {aka long unsigned int}' may alter its value [-Wconversion]
     if (pow(3,num) < b.count()) return 1;
                      ~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:158:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^

• Subtask 1: 100 / 100