Submission #532704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
532704	2022-03-03T16:35:53 Z	ivan24	Scales (IOI15_scales)	C++14	72.619 / 100	476 ms	540 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	455 ms	452 KB	Output is partially correct
2	Partially correct	390 ms	460 KB	Output is partially correct
3	Partially correct	431 ms	460 KB	Output is partially correct
4	Correct	393 ms	460 KB	Output is correct
5	Partially correct	441 ms	464 KB	Output is partially correct
6	Partially correct	400 ms	460 KB	Output is partially correct
7	Partially correct	412 ms	448 KB	Output is partially correct
8	Partially correct	424 ms	452 KB	Output is partially correct
9	Partially correct	465 ms	460 KB	Output is partially correct
10	Partially correct	417 ms	460 KB	Output is partially correct
11	Correct	423 ms	332 KB	Output is correct
12	Partially correct	429 ms	460 KB	Output is partially correct
13	Partially correct	423 ms	460 KB	Output is partially correct
14	Partially correct	396 ms	448 KB	Output is partially correct
15	Partially correct	406 ms	468 KB	Output is partially correct
16	Partially correct	425 ms	464 KB	Output is partially correct
17	Partially correct	464 ms	460 KB	Output is partially correct
18	Partially correct	394 ms	460 KB	Output is partially correct
19	Partially correct	462 ms	460 KB	Output is partially correct
20	Partially correct	389 ms	468 KB	Output is partially correct
21	Partially correct	470 ms	448 KB	Output is partially correct
22	Partially correct	391 ms	416 KB	Output is partially correct
23	Partially correct	427 ms	460 KB	Output is partially correct
24	Partially correct	440 ms	464 KB	Output is partially correct
25	Partially correct	415 ms	460 KB	Output is partially correct
26	Partially correct	411 ms	460 KB	Output is partially correct
27	Partially correct	419 ms	460 KB	Output is partially correct
28	Partially correct	429 ms	452 KB	Output is partially correct
29	Partially correct	417 ms	460 KB	Output is partially correct
30	Partially correct	410 ms	460 KB	Output is partially correct
31	Partially correct	417 ms	448 KB	Output is partially correct
32	Partially correct	397 ms	460 KB	Output is partially correct
33	Correct	408 ms	464 KB	Output is correct
34	Partially correct	438 ms	460 KB	Output is partially correct
35	Partially correct	430 ms	540 KB	Output is partially correct
36	Partially correct	414 ms	456 KB	Output is partially correct
37	Correct	407 ms	456 KB	Output is correct
38	Partially correct	412 ms	460 KB	Output is partially correct
39	Partially correct	401 ms	460 KB	Output is partially correct
40	Partially correct	476 ms	460 KB	Output is partially correct