Submission #199975

#	Time	Username	Problem	Language	Result	Execution time	Memory
199975		Mercenary	저울 (IOI15_scales)	C++14	0 / 100	1117 ms	211272 KiB

scales

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

#include"scales.h"

#define mp make_pair
#define pb push_back
const int maxn = 2e6;
vector<vector<int>> perm;

vector<vector<int>> p(1);

int a[maxn] , b[maxn][3];
vector<pair<int,vector<int>>> query;
int ans[maxn];

vector<vector<int>> GetLig(vector<int> & p , vector<int> &a){
    vector<vector<int>> res(3);
    for(int i = 0 ; i < 3 ; ++i){
        for(auto & c : p){
            if(perm[c][a[i]] == min({perm[c][a[0]] , perm[c][a[1]] , perm[c][a[2]]})){
                res[i].pb(c);
            }
        }
    }
    return res;
}

vector<vector<int>> GetHea(vector<int> & p , vector<int> &a){
    vector<vector<int>> res(3);
    for(int i = 0 ; i < 3 ; ++i){
        for(auto & c : p){
            if(perm[c][a[i]] == max({perm[c][a[0]] , perm[c][a[1]] , perm[c][a[2]]})){
                res[i].pb(c);
            }
        }
    }
    return res;
}

vector<vector<int>> GetMed(vector<int> & p , vector<int> &a){
    vector<vector<int>> res(3);
    for(int i = 0 ; i < 3 ; ++i){
        for(auto & c : p){
            if(perm[c][a[i]] != min({perm[c][a[0]] , perm[c][a[1]] , perm[c][a[2]]}) &&
               perm[c][a[i]] != max({perm[c][a[0]] , perm[c][a[1]] , perm[c][a[2]]})){
                res[i].pb(c);
            }
        }
    }
    return res;
}

vector<vector<int>> Get(vector<int> &p , int q){
    if(query[q].first == 0)return GetLig(p,query[q].second);
    if(query[q].first == 1)return GetHea(p,query[q].second);
    if(query[q].first == 2)return GetMed(p,query[q].second);
}

int build(int pos , int x){
    if(p[pos].size() <= 1)return 0;
    if(pos == 6)return 10;
    pair<int,int> res = mp(6 , 0);
    for(int i = 0 ; i < (int)query.size() ; ++i){
        auto tmp = Get(p[x] , i);
        int sz = p.size();
        for(auto &c : tmp)p.pb(c);
        int ans = 0;
        for(int j = 0 ; j < 3 ; ++j){
            b[x][j] = sz + j;
            ans = max(ans,build(pos+1,sz+j));
        }
        res = min(res,mp(ans,i));
    }
    ans[x] = res.second;
}

void go(int x){
    if(p[x].size() == 1 || 1){
        int *ans = new int[6];
        for(int i = 0; i < 6; i++) ans[perm[p[x][0]][i]] = i + 1;
        answer(ans);
        return;
    }
    auto q = query[ans[x]];
    auto tmp = Get(p[x] , ans[x]);
    int id;
    if(q.first == 0)id = getLightest(q.second[0]+1,q.second[1]+1,q.second[2]+1);
    else if(q.first == 1)id = getHeaviest(q.second[0]+1,q.second[1]+1,q.second[2]+1);
    else if(q.first == 2)id = getMedian(q.second[0]+1,q.second[1]+1,q.second[2]+1);
    --id;
    for(int i = 0 ; i < 3 ; ++i){
        if(q.second[i] == id){
            go(b[x][i]);
            return;
        }
    }
}

void init(int T) {
    vector<int> tmp(6);iota(tmp.begin(),tmp.end(),0);
    do{
        perm.pb(tmp);
    }while(next_permutation(tmp.begin(),tmp.end()));
    p[0].resize(720);iota(p[0].begin(),p[0].end(),0);
    for(int i = 0 ; i < (1 << 6) ; ++i){
        if(__builtin_popcount(i) == 3){
            vector<int> tmp;
            for(int j = 0 ; j < 10 ; ++j){
                if(i & (1 << j))tmp.pb(j);
            }
            for(int j = 0 ; j < 3 ; ++j){
                query.pb(mp(j,tmp));
            }
        }
    }
    build(0,0);
}

void orderCoins() {
    go(0);
}

Compilation message (stderr)

scales.cpp: In function 'std::vector<std::vector<int> > GetLig(std::vector<int>&, std::vector<int>&)':
scales.cpp:17:60: warning: declaration of 'a' shadows a global declaration [-Wshadow]
 vector<vector<int>> GetLig(vector<int> & p , vector<int> &a){
                                                            ^
scales.cpp:13:5: note: shadowed declaration is here
 int a[maxn] , b[maxn][3];
     ^
scales.cpp:17:60: warning: declaration of 'p' shadows a global declaration [-Wshadow]
 vector<vector<int>> GetLig(vector<int> & p , vector<int> &a){
                                                            ^
scales.cpp:11:21: note: shadowed declaration is here
 vector<vector<int>> p(1);
                     ^
scales.cpp: In function 'std::vector<std::vector<int> > GetHea(std::vector<int>&, std::vector<int>&)':
scales.cpp:29:60: warning: declaration of 'a' shadows a global declaration [-Wshadow]
 vector<vector<int>> GetHea(vector<int> & p , vector<int> &a){
                                                            ^
scales.cpp:13:5: note: shadowed declaration is here
 int a[maxn] , b[maxn][3];
     ^
scales.cpp:29:60: warning: declaration of 'p' shadows a global declaration [-Wshadow]
 vector<vector<int>> GetHea(vector<int> & p , vector<int> &a){
                                                            ^
scales.cpp:11:21: note: shadowed declaration is here
 vector<vector<int>> p(1);
                     ^
scales.cpp: In function 'std::vector<std::vector<int> > GetMed(std::vector<int>&, std::vector<int>&)':
scales.cpp:41:60: warning: declaration of 'a' shadows a global declaration [-Wshadow]
 vector<vector<int>> GetMed(vector<int> & p , vector<int> &a){
                                                            ^
scales.cpp:13:5: note: shadowed declaration is here
 int a[maxn] , b[maxn][3];
     ^
scales.cpp:41:60: warning: declaration of 'p' shadows a global declaration [-Wshadow]
 vector<vector<int>> GetMed(vector<int> & p , vector<int> &a){
                                                            ^
scales.cpp:11:21: note: shadowed declaration is here
 vector<vector<int>> p(1);
                     ^
scales.cpp: In function 'std::vector<std::vector<int> > Get(std::vector<int>&, int)':
scales.cpp:54:47: warning: declaration of 'p' shadows a global declaration [-Wshadow]
 vector<vector<int>> Get(vector<int> &p , int q){
                                               ^
scales.cpp:11:21: note: shadowed declaration is here
 vector<vector<int>> p(1);
                     ^
scales.cpp: In function 'int build(int, int)':
scales.cpp:66:24: warning: conversion to 'int' from 'std::vector<std::vector<int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         int sz = p.size();
                  ~~~~~~^~
scales.cpp:68:13: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
         int ans = 0;
             ^~~
scales.cpp:15:5: note: shadowed declaration is here
 int ans[maxn];
     ^~~
scales.cpp: In function 'void go(int)':
scales.cpp:80:14: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
         int *ans = new int[6];
              ^~~
scales.cpp:15:5: note: shadowed declaration is here
 int ans[maxn];
     ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:108:25: warning: declaration of 'tmp' shadows a previous local [-Wshadow]
             vector<int> tmp;
                         ^~~
scales.cpp:101:17: note: shadowed declaration is here
     vector<int> tmp(6);iota(tmp.begin(),tmp.end(),0);
                 ^~~
scales.cpp:100:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^
scales.cpp: In function 'std::vector<std::vector<int> > Get(std::vector<int>&, int)':
scales.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
scales.cpp: In function 'int build(int, int)':
scales.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 100