Submission #532704

#	Time	Username	Problem	Language	Result	Execution time	Memory
532704		ivan24	Scales (IOI15_scales)	C++14	72.62 / 100	476 ms	540 KiB

scales

#include "scales.h"
#include<bits/stdc++.h>
using namespace std;

using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

ll min (ll x, ll y){
    return ((x < y) ? x : y);
}

ll max (ll x, ll y){
    return ((x > y) ? x : y);
}

const ll INF = 1e18;

class Solution {
private:
    vi w;
    vi idx;
public:
    Solution (){

    }
    Solution (vi _w): w(_w){
        idx.resize(7);
        for (ll i = 0; 6 > i; i++) idx[w[i]] = i;
    }
    ll test (ll type, vi params){
        if (3 > type){
            vii v;
            for (auto i: params) v.emplace_back(idx[i],i);
            sort(v.begin(),v.end());
            return v[type].S;
        }else{
            vii v;
            for (auto i: params) v.emplace_back(idx[i],i);
            v.pop_back();
            sort(v.begin(),v.end());
            ll target = idx[params[3]];
            for (ll i = 0; v.size() > i; i++){
                if (v[i].F > target) return v[i].S;
            }
            return v[0].S;
        }
    }
    vi get_w(){
        return w;
    }
};

class SolutionSet {
private:
    vector<Solution> space;
    vector<pair<ll,vi> > history;
    ll try_test (ll type, vi params) {
        ll res = 0;
        vi vcur; vcur.assign(7,0);
        for (auto i: space){
            ll cur = i.test(type,params);
            vcur[cur]++;
        }
        for (auto i: vcur) res += i*i;
        return res;
    }
public:
    SolutionSet(){
        vi cur_w;
        for (ll i = 0; 6 > i; i++) cur_w.push_back(i+1);
        do{
            space.push_back(Solution(cur_w));
        }while (next_permutation(cur_w.begin(),cur_w.end()));
    }
    ll get_size(){
        return space.size();
    }
    void best_test(){
        ll cur = INF, curt;
        vi curparam;
        for (ll t = 0; 3 > t; t++){
            for (ll i = 1; 6 >= i; i++){
                for (ll j = i+1; 6 >= j; j++){
                    for (ll k = j+1; 6 >= k; k++){
                        ll curscore = try_test(t,vi{i,j,k});
                        if (curscore < cur){
                            cur = curscore; curt = t; curparam = vi{i,j,k};
                        }
                    }
                }
            }
        }

        for (ll i = 1; 6 >= i; i++){
            for (ll j = i+1; 6 >= j; j++){
                for (ll k = j+1; 6 >= k; k++){
                    for (ll o = 1; 6 >= o; o++){
                        if ((o == i) || (o == j) || (o == k)) continue;
                        ll curscore = try_test(3,vi{i,j,k,o});
                        if (curscore < cur){
                            cur = curscore; curt = 3; curparam = vi{i,j,k,o};
                        }
                    }
                }
            }
        }

        ll res;
        if (curt == 0){
            res = getLightest(curparam[0],curparam[1],curparam[2]);
        }else if (curt == 1){
            res = getMedian(curparam[0],curparam[1],curparam[2]);
        }else if (curt == 2){
            res = getHeaviest(curparam[0],curparam[1],curparam[2]);
        }else
            res = getNextLightest(curparam[0],curparam[1],curparam[2],curparam[3]);

        vector<Solution> newspace;
        for (auto i: space){
            if (i.test(curt,curparam) == res) newspace.push_back(i);
        }
        space = newspace;
    }

    vi answer(){
        return space[0].get_w();
    }
};

void init(int t) {
    /* ... */
}

void orderCoins() {
    /* ... */
    SolutionSet mySol;

    while (mySol.get_size() != 1){
        mySol.best_test();
    }

    vi res = mySol.answer();
    int w[] = {1,2,3,4,5,6};
    for (ll i = 0; 6 > i; i++) w[i] = res[i];
    answer(w);

    /*
    ll p_r = 0, p_l = 0;
    while (p_r != 3 || p_l != 3){
        if (p_r == 3){
            w[p_l+p_r] = l_ar[p_l];
            p_l++;
        }else if (p_l == 3){
            w[p_l+p_r] = r_ar[p_r];
            p_r++;
        }else{
            ll cur;
            if (p_l == 2 && p_r == 2){
                cur = getMedian(l_ar[1],l_ar[2],r_ar[2]);
            }else if (p_r == 2){
                cur = getLightest(l_ar[p_l],l_ar[p_l+1],r_ar[p_r]);
            }else if (p_l == 2){
                cur = getLightest(l_ar[p_l],r_ar[p_r+1],r_ar[p_r]);
            }else{
                cur = getLightest(l_ar[p_l],r_ar[p_r+1],r_ar[p_r]);
            }
            w[p_l+p_r] = cur;
            if (cur == l_ar[p_l]){
                p_l++;
            }else{
                p_r++;
            }
        }
    }

    w[5] = 21;
    for (ll i = 0; 4 >= i; i++) w[5] -= w[i];
    */
}

Compilation message (stderr)

scales.cpp: In member function 'll Solution::test(ll, vi)':
scales.cpp:48:37: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   48 |             for (ll i = 0; v.size() > i; i++){
      |                            ~~~~~~~~~^~~
scales.cpp: In member function 'void SolutionSet::best_test()':
scales.cpp:116:66: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  116 |             res = getLightest(curparam[0],curparam[1],curparam[2]);
      |                                                                  ^
scales.cpp:116:66: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:116:66: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:118:64: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  118 |             res = getMedian(curparam[0],curparam[1],curparam[2]);
      |                                                                ^
scales.cpp:118:64: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:118:64: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:120:66: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  120 |             res = getHeaviest(curparam[0],curparam[1],curparam[2]);
      |                                                                  ^
scales.cpp:120:66: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:120:66: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:122:82: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  122 |             res = getNextLightest(curparam[0],curparam[1],curparam[2],curparam[3]);
      |                                                                                  ^
scales.cpp:122:82: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:122:82: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:122:82: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp: In function 'void init(int)':
scales.cpp:136:15: warning: unused parameter 't' [-Wunused-parameter]
  136 | void init(int t) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:150:44: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
  150 |     for (ll i = 0; 6 > i; i++) w[i] = res[i];
      |                                            ^
scales.cpp: In member function 'void SolutionSet::best_test()':
scales.cpp:126:23: warning: 'curt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  126 |             if (i.test(curt,curparam) == res) newspace.push_back(i);
      |                 ~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 72.619048 / 100