Submission #777694

#	Time	Username	Problem	Language	Result	Execution time	Memory
777694		boris_mihov	Scales (IOI15_scales)	C++17	75.60 / 100	301 ms	7128 KiB

scales

#include "scales.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <map>
#include <set>

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

typedef long long llong;
const int N = 6;

struct Permutation
{
    int vals[N];
    Permutation(){}
    Permutation(int _vals[])
    {
        for (int i = 0 ; i < N ; ++i)
        {
            vals[i] = _vals[i];
        }
    }

    int getLightest(int a, int b)
    {
        int value = std::min(vals[a - 1], vals[b - 1]);
        if (vals[a - 1] == value) return a;
        if (vals[b - 1] == value) return b;
    }
    
    int getLightest(int a, int b, int c)
    {
        int value = std::min(std::min(vals[a - 1], vals[b - 1]), vals[c - 1]);
        if (vals[a - 1] == value) return a;
        if (vals[b - 1] == value) return b;
        if (vals[c - 1] == value) return c;
    }
    
    int getHeaviest(int a, int b, int c)
    {
        int value = std::max(std::max(vals[a - 1], vals[b - 1]), vals[c - 1]);
        if (vals[a - 1] == value) return a;
        if (vals[b - 1] == value) return b;
        if (vals[c - 1] == value) return c;
    }

    int getMedian(int a, int b, int c)
    {
        int min = getLightest(a, b, c);
        int max = getHeaviest(a, b, c);
        if (min != a && max != a) return a;
        if (min != b && max != b) return b;
        if (min != c && max != c) return c;
    }

    int getNextLightest(int a, int b, int c, int d)
    {
        if (std::max(std::max(vals[a - 1], vals[b - 1]), std::max(vals[c - 1], vals[d - 1])) == vals[d - 1])
        {
            return getLightest(a, b, c);
        }

        std::vector <int> coins;
        if (vals[a - 1] > vals[d - 1])
        {
            coins.push_back(a);
        }

        if (vals[b - 1] > vals[d - 1])
        {
            coins.push_back(b);
        }

        if (vals[c - 1] > vals[d - 1])
        {
            coins.push_back(c);
        }

        if (coins.size() == 1) return coins[0];
        if (coins.size() == 2) return getLightest(coins[0], coins[1]);
        if (coins.size() == 3) return getLightest(coins[0], coins[1], coins[2]);
    }

    int getRes(int t, int a, int b, int c, int d)
    {
        if (t == 0) return getLightest(a, b, c);
        if (t == 1) return getHeaviest(a, b, c);
        if (t == 2) return getMedian(a, b, c);
        if (t == 3) return getNextLightest(a, b, c, d);
    }

    friend bool operator == (const Permutation &a, const Permutation &b)
    {
        for (int i = 0 ; i < N ; ++i)
        {
            if (a.vals[i] != b.vals[i])
            {
                return false;
            }
        }

        return true;
    }

    friend bool operator < (const Permutation &a, const Permutation &b)
    {
        for (int i = 0 ; i < N ; ++i)
        {
            if (a.vals[i] < b.vals[i]) return true;
            if (a.vals[i] > b.vals[i]) return false;
        }

        return false;
    }
};

struct Mask
{
    std::vector <Permutation> perms;
    std::vector <Mask> split(int t, int a, int b, int c, int d = 0)
    {
        std::vector <Mask> res;
        std::vector <int> perm;
        perm.resize(perms.size(), 0);
        std::iota(perm.begin(), perm.end(), 0);
        std::sort(perm.begin(), perm.end(), [&](int x, int y)
        {
            return perms[x].getRes(t, a, b, c, d) < perms[y].getRes(t, a, b, c, d);
        });

        for (int i = 0 ; i < perms.size() ; ++i)
        {
            if (res.empty() || res.back().perms.back().getRes(t, a, b, c, d) != perms[perm[i]].getRes(t, a, b, c, d))
            {
                Mask newMask;
                res.push_back(newMask);
            }

            res.back().perms.push_back(perms[perm[i]]);
        }

        return res;
    }

    Mask getSplit(int wanted, int t, int a, int b, int c, int d)
    {
        std::vector <Mask> res;
        std::vector <int> perm;
        perm.resize(perms.size(), 0);
        std::iota(perm.begin(), perm.end(), 0);
        std::sort(perm.begin(), perm.end(), [&](int x, int y)
        {
            return perms[x].getRes(t, a, b, c, d) < perms[y].getRes(t, a, b, c, d);
        });

        for (int i = 0 ; i < perms.size() ; ++i)
        {
            if (res.empty() || res.back().perms.back().getRes(t, a, b, c, d) != perms[perm[i]].getRes(t, a, b, c, d))
            {
                Mask newMask;
                res.push_back(newMask);
            }

            res.back().perms.push_back(perms[perm[i]]);
        }

        for (int i = 0 ; i < res.size() ; ++i)
        {
            if (res[i].perms.back().getRes(t, a, b, c, d) == wanted)
            {
                return res[i];
            }
        }
    }

    friend bool operator < (const Mask &a, const Mask &b)
    {
        if (a.perms.size() < b.perms.size()) return true;
        if (a.perms.size() > b.perms.size()) return false;

        for (int i = 0 ; i < a.perms.size() ; ++i)
        {
            if (a.perms[i] < b.perms[i]) return true;
            if (!(a.perms[i] == b.perms[i])) return false;
        }

        return false;
    }
};

struct Operation
{
    int t, a, b, c, d;
    Operation(){}
    Operation(int _t, int _a, int _b, int _c)
    {
        t = _t;
        a = _a;
        b = _b;
        c = _c;
        d = 0;
    }

    Operation(int _t, int _a, int _b, int _c, int _d)
    {
        t = _t;
        a = _a;
        b = _b;
        c = _c;
        d = _d;
    }

    friend bool operator < (const Operation &x, const Operation &y)
    {
        return x.t < y.t || (x.t == y.t && x.a < y.a) || (x.t == y.t && x.a == y.a && x.b < y.b) || (x.t == y.t && x.a == y.a && x.b == y.b && x.c < y.c) || (x.t == y.t && x.a == y.a && x.b == y.b && x.c == y.c && x.d < y.d);
    }
};

const int DP_CONST = 10;
const int T_CONST = 50;

std::map <Mask, int> mem;
std::map <Mask, Operation> next;
std::mt19937 rng(69420);

int f(Mask mask)
{
    if (mask.perms.size() == 1)
    {
        return 0;
    }

    if (mem.count(mask))
    {
        return mem[mask];
    }

    std::set <Operation> used;
    std::vector <std::pair <std::vector <Mask>, Operation>> received;
    for (int t = 0 ; t < 3 ; ++t)
    {
        for (int i = 0 ; i < T_CONST ; ++i)
        {
            int a, b, c;
            do
            {
                a = rng()%N + 1;
                b = rng()%(N - 1) + 1;
                if (b >= a) b++;

                c = rng()%(N - 2) + 1;
                if (c >= std::min(a, b)) c++;
                if (c >= std::max(a, b)) c++;

            } while(used.count({t, a, b, c, 0}));

            used.insert({t, a, b, c, 0});
            Operation curr(t, a, b, c);
            received.push_back({mask.split(t, a, b, c), curr});

        };
    }

    for (int i = 0 ; i < T_CONST ; ++i)
    {
        int a, b, c, d;
        do
        {
            a = rng()%N + 1;
            b = rng()%(N - 1) + 1;
            if (b >= a) b++;

            c = rng()%(N - 2) + 1;
            if (c >= std::min(a, b)) c++;
            if (c >= std::max(a, b)) c++;
            
            d = rng()%N + 1;

        } while(d == a || d == b || d == c || used.count({3, a, b, c, d}));

        used.insert({3, a, b, c, d});
        Operation curr(3, a, b, c, d);
        received.push_back({mask.split(3, a, b, c, d), curr});
    };

    std::sort(received.begin(), received.end(), [&](auto x, auto y)
    {
        int szX = 0;
        int szY = 0;
        
        for (int i = 0 ; i < x.first.size() ; ++i)
        {
            szX = std::max(szX, (int)x.first[i].perms.size());
        }

        for (int i = 0 ; i < y.first.size() ; ++i)
        {
            szY = std::max(szY, (int)y.first[i].perms.size());
        }

        return szX < szY;
    });

    int res = 0;
    next[mask] = received[0].second;
    for (const auto &curr : received[0].first)
    {
        res = std::max(res, f(curr));
    }

    res++;
    mem[mask] = res;
    return res;
}

int perm[N];
void init(int T) 
{
    Mask curr;
    std::iota(perm, perm + N, 1);
    do
    {
        Permutation currP(perm);
        curr.perms.push_back(currP);
    } while (std::next_permutation(perm, perm + N));
    f(curr);
}

int w[N];
int wRes[N];
void orderCoins() 
{
    Mask curr;
    std::iota(perm, perm + N, 1);
    do
    {
        Permutation currP(perm);
        curr.perms.push_back(currP);
    } while (std::next_permutation(perm, perm + N));

    while (curr.perms.size() > 1)
    {
        int res;
        Operation op = next[curr];
        if (op.t == 0)
        {
            res = getLightest(op.a, op.b, op.c);
        } 

        if (op.t == 1)
        {
            res = getHeaviest(op.a, op.b, op.c);
        } 

        if (op.t == 2)
        {
            res = getMedian(op.a, op.b, op.c);
        } 

        if (op.t == 3)
        {
            res = getNextLightest(op.a, op.b, op.c, op.d);
        } 

        curr = curr.getSplit(res, op.t, op.a, op.b, op.c, op.d);
    }   

    assert(curr.perms.size() == 1);
    for (int i = 0 ; i < N ; ++i)
    {
        wRes[i] = curr.perms[0].vals[i];
    }

    for (int i = 0 ; i < N ; ++i)
    {
        w[wRes[i] - 1] = i + 1;
    }

    answer(w);
}

Compilation message (stderr)

scales.cpp: In member function 'std::vector<Mask> Mask::split(int, int, int, int, int)':
scales.cpp:136:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Permutation>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for (int i = 0 ; i < perms.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~
scales.cpp: In member function 'Mask Mask::getSplit(int, int, int, int, int, int)':
scales.cpp:161:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Permutation>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         for (int i = 0 ; i < perms.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~
scales.cpp:172:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Mask>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |         for (int i = 0 ; i < res.size() ; ++i)
      |                          ~~^~~~~~~~~~~~
scales.cpp: In function 'bool operator<(const Mask&, const Mask&)':
scales.cpp:186:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Permutation>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |         for (int i = 0 ; i < a.perms.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~~~
scales.cpp: In function 'int f(Mask)':
scales.cpp:252:29: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  252 |                 a = rng()%N + 1;
      |                     ~~~~~~~~^~~
scales.cpp:253:35: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  253 |                 b = rng()%(N - 1) + 1;
      |                     ~~~~~~~~~~~~~~^~~
scales.cpp:274:25: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  274 |             a = rng()%N + 1;
      |                 ~~~~~~~~^~~
scales.cpp:275:31: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  275 |             b = rng()%(N - 1) + 1;
      |                 ~~~~~~~~~~~~~~^~~
scales.cpp:282:25: warning: conversion from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  282 |             d = rng()%N + 1;
      |                 ~~~~~~~~^~~
scales.cpp: In function 'void init(int)':
scales.cpp:322:15: warning: unused parameter 'T' [-Wunused-parameter]
  322 | void init(int T)
      |           ~~~~^
scales.cpp: In instantiation of 'f(Mask)::<lambda(auto:1, auto:2)> [with auto:1 = std::pair<std::vector<Mask>, Operation>; auto:2 = std::pair<std::vector<Mask>, Operation>]':
/usr/include/c++/10/bits/predefined_ops.h:156:30:   required from 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<std::vector<Mask>, Operation>*, std::vector<std::pair<std::vector<Mask>, Operation> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<std::vector<Mask>, Operation>*, std::vector<std::pair<std::vector<Mask>, Operation> > >; _Compare = f(Mask)::<lambda(auto:1, auto:2)>]'
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<std::vector<Mask>, Operation>*, std::vector<std::pair<std::vector<Mask>, Operation> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<f(Mask)::<lambda(auto:1, auto:2)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::vector<Mask>, Operation>*, std::vector<std::pair<std::vector<Mask>, Operation> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<f(Mask)::<lambda(auto:1, auto:2)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::vector<Mask>, Operation>*, std::vector<std::pair<std::vector<Mask>, Operation> > >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<f(Mask)::<lambda(auto:1, auto:2)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::pair<std::vector<Mask>, Operation>*, std::vector<std::pair<std::vector<Mask>, Operation> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<f(Mask)::<lambda(auto:1, auto:2)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::pair<std::vector<Mask>, Operation>*, std::vector<std::pair<std::vector<Mask>, Operation> > >; _Compare = f(Mask)::<lambda(auto:1, auto:2)>]'
scales.cpp:307:6:   required from here
scales.cpp:296:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Mask>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  296 |         for (int i = 0 ; i < x.first.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~~~
scales.cpp:301:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Mask>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  301 |         for (int i = 0 ; i < y.first.size() ; ++i)
      |                          ~~^~~~~~~~~~~~~~~~
scales.cpp: In member function 'int Permutation::getRes(int, int, int, int, int)':
scales.cpp:95:5: warning: control reaches end of non-void function [-Wreturn-type]
   95 |     }
      |     ^
scales.cpp: In member function 'int Permutation::getLightest(int, int, int)':
scales.cpp:42:5: warning: control reaches end of non-void function [-Wreturn-type]
   42 |     }
      |     ^
scales.cpp: In member function 'int Permutation::getHeaviest(int, int, int)':
scales.cpp:50:5: warning: control reaches end of non-void function [-Wreturn-type]
   50 |     }
      |     ^
scales.cpp: In member function 'int Permutation::getMedian(int, int, int)':
scales.cpp:59:5: warning: control reaches end of non-void function [-Wreturn-type]
   59 |     }
      |     ^
scales.cpp: In member function 'int Permutation::getNextLightest(int, int, int, int)':
scales.cpp:68:27: warning: control reaches end of non-void function [-Wreturn-type]
   68 |         std::vector <int> coins;
      |                           ^~~~~
scales.cpp: In member function 'int Permutation::getLightest(int, int)':
scales.cpp:34:5: warning: control reaches end of non-void function [-Wreturn-type]
   34 |     }
      |     ^
scales.cpp: In member function 'Mask Mask::getSplit(int, int, int, int, int, int)':
scales.cpp:152:28: warning: control reaches end of non-void function [-Wreturn-type]
  152 |         std::vector <Mask> res;
      |                            ^~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:174:13: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  174 |             if (res[i].perms.back().getRes(t, a, b, c, d) == wanted)
      |             ^~
scales.cpp:348:13: note: 'res' was declared here
  348 |         int res;
      |             ^~~

• Subtask 1: 75.595238 / 100