Submission #824089

#	Time	Username	Problem	Language	Result	Execution time	Memory
824089		Khizri	Scales (IOI15_scales)	C++17	71.43 / 100	16 ms	5448 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=2e5+5;
vector<vector<int>>vt[mxn];
int L[mxn],R[mxn],M[mxn],iq[mxn],jq[mxn],kq[mxn],dq[mxn],op[mxn],nxt=1;
int fnd(int i,int j,int k,int a,vector<int>&vt){
    if(max(vt[i],max(vt[j],vt[k]))<vt[a]){
        int mn=min(vt[i],min(vt[j],vt[k]));
        if(mn==vt[i]) return i;
        if(mn==vt[j]) return j;
        return k;
    }
    vector<int>v={vt[i],vt[j],vt[k]};
    sort(all(v));
    int mn;
    if(v[0]>vt[a]){
        mn=v[0];
    }
    else if(v[1]>vt[a]){
        mn=v[1];
    }
    else{
        mn=v[2];
    }
    if(mn==vt[i]) return i;
    if(mn==vt[j]) return j;
    return k;
}
void build(int node){
    ll mx=INF;
    int ix,jx,kx,dx=0;
    for(int i=0;i<6;i++){
        for(int j=i+1;j<6;j++){
            for(int k=j+1;k<6;k++){
                ll a=0,b=0,c=0;
                for(int idx=0;idx<vt[node].size();idx++){
                    if(vt[node][idx][i]>max(vt[node][idx][j],vt[node][idx][k])){
                        a++;
                    }
                    else if(vt[node][idx][j]>max(vt[node][idx][i],vt[node][idx][k])){
                        b++;
                    }
                    else{
                        c++;
                    }
                }
                if(max({a,b,c})<mx){
                    mx=max({a,b,c});
                    op[node]=1;
                    ix=i,jx=j,kx=k;
                }
            }
        }
    }
    for(int i=0;i<6;i++){
        for(int j=i+1;j<6;j++){
            for(int k=j+1;k<6;k++){
                ll a=0,b=0,c=0;
                for(int idx=0;idx<vt[node].size();idx++){
                    if(vt[node][idx][i]<min(vt[node][idx][j],vt[node][idx][k])){
                        a++;
                    }
                    else if(vt[node][idx][j]<min(vt[node][idx][i],vt[node][idx][k])){
                        b++;
                    }
                    else{
                        c++;
                    }
                }
                if(max({a,b,c})<mx){
                    mx=max({a,b,c});
                    op[node]=2;
                    ix=i,jx=j,kx=k;
                }
            }
        }
    }
    for(int i=0;i<6;i++){
        for(int j=i+1;j<6;j++){
            for(int k=j+1;k<6;k++){
                ll a=0,b=0,c=0;
                for(int idx=0;idx<vt[node].size();idx++){
                    if(vt[node][idx][i]>min(vt[node][idx][j],vt[node][idx][k])&&vt[node][idx][i]<max(vt[node][idx][j],vt[node][idx][k])){
                        a++;
                    }
                    else if(vt[node][idx][j]>min(vt[node][idx][i],vt[node][idx][k])&&vt[node][idx][j]<max(vt[node][idx][i],vt[node][idx][k])){
                        b++;
                    }
                    else{
                        c++;
                    }
                }
                if(max({a,b,c})<mx){
                    mx=max({a,b,c});
                    op[node]=3;
                    ix=i,jx=j,kx=k;
                }
            }
        }
    }
    for(int d=0;d<6;d++){
        for(int i=0;i<6;i++){
            if(i==d) continue;
            for(int j=i+1;j<6;j++){
                if(j==d) continue;
                for(int k=j+1;k<6;k++){
                    if(k==d) continue;
                    ll a=0,b=0,c=0;
                    for(int idx=0;idx<vt[node].size();idx++){
                        int res=fnd(i,j,k,d,vt[node][idx]);
                        if(res==i){
                            a++;
                        }
                        else if(res==j){
                            b++;
                        }
                        else{
                            c++;
                        }
                    }
                    if(max({a,b,c})<mx){
                        mx=max({a,b,c});
                        op[node]=4;
                        ix=i,jx=j,kx=k,dx=d;
                    }
                }
            }
        }
    }
    L[node]=++nxt;
    M[node]=++nxt;
    R[node]=++nxt;
    iq[node]=ix;
    jq[node]=jx;
    kq[node]=kx;
    dq[node]=dx;
    //cout<<L[node]<<' '<<M[node]<<' '<<R[node]<<endl;
    if(op[node]==1){
        for(int idx=0;idx<vt[node].size();idx++){
            if(vt[node][idx][ix]>max(vt[node][idx][jx],vt[node][idx][kx])){
                vt[L[node]].pb(vt[node][idx]);
            }
            else if(vt[node][idx][jx]>max(vt[node][idx][ix],vt[node][idx][kx])){
                vt[M[node]].pb(vt[node][idx]);
            }
            else{
                vt[R[node]].pb(vt[node][idx]);
            }
        }
    }
    else if(op[node]==2){
        for(int idx=0;idx<vt[node].size();idx++){
            if(vt[node][idx][ix]<min(vt[node][idx][jx],vt[node][idx][kx])){
                vt[L[node]].pb(vt[node][idx]);
            }
            else if(vt[node][idx][jx]<min(vt[node][idx][ix],vt[node][idx][kx])){
                vt[M[node]].pb(vt[node][idx]);
            }
            else{
                vt[R[node]].pb(vt[node][idx]);
            }
        }
    }
    else if(op[node]==3){
        for(int idx=0;idx<vt[node].size();idx++){
            if(vt[node][idx][ix]>min(vt[node][idx][jx],vt[node][idx][kx])&&vt[node][idx][ix]<max(vt[node][idx][jx],vt[node][idx][kx])){
                vt[L[node]].pb(vt[node][idx]);
            }
            else if(vt[node][idx][jx]>min(vt[node][idx][ix],vt[node][idx][kx])&&vt[node][idx][jx]<max(vt[node][idx][ix],vt[node][idx][kx])){
                vt[M[node]].pb(vt[node][idx]);
            }
            else{
                vt[R[node]].pb(vt[node][idx]);
            }
        }
    }
    else{
        for(int idx=0;idx<vt[node].size();idx++){
            int res=fnd(ix,jx,kx,dx,vt[node][idx]);
            if(res==ix){
                vt[L[node]].pb(vt[node][idx]);
            }
            else if(res==jx){
                vt[M[node]].pb(vt[node][idx]);
            }
            else{
                vt[R[node]].pb(vt[node][idx]);
            }
        }
    }
    if(vt[L[node]].size()>1){
        build(L[node]);
    }
    if(vt[M[node]].size()>1){
        build(M[node]);
    }
    if(vt[R[node]].size()>1){
        build(R[node]);
    }
}
vector<int>query(int node){
    if(vt[node].size()==1){
        return vt[node][0];
    }
    //cout<<vt[node].size()<<endl;
    int x;
    if(op[node]==1){
        //cout<<1<<' '<<iq[node]+1<<' '<<jq[node]+1<<' '<<kq[node]+1<<endl;
        x=getHeaviest(iq[node]+1,jq[node]+1,kq[node]+1);
    }
    else if(op[node]==2){
        //cout<<0<<' '<<iq[node]+1<<' '<<jq[node]+1<<' '<<kq[node]+1<<endl;
        x=getLightest(iq[node]+1,jq[node]+1,kq[node]+1);
    }
    else if(op[node]==3){
        x=getMedian(iq[node]+1,jq[node]+1,kq[node]+1);
    }
    else{
        x=getNextLightest(iq[node]+1,jq[node]+1,kq[node]+1,dq[node]+1);
    }
    if(x==iq[node]+1){
        return query(L[node]);
    }
    else if(x==jq[node]+1){
        return query(M[node]);
    }
    else{
        return query(R[node]);
    }
}
void init(int T) {
    vector<int>v(6);
    iota(all(v),1);
    do{
        vt[1].pb(v);
    }while(next_permutation(all(v)));
    build(1);
}

void orderCoins() {
    vector<int>vt=query(1);
    int arr[6];
    for(int i=0;i<6;i++){
        arr[vt[i]-1]=i+1;
    }
    answer(arr);
}
/*
g++ scales.cpp grader.cpp ; .\a.exe
*/

Compilation message (stderr)

scales.cpp: In function 'int fnd(int, int, int, int, std::vector<int>&)':
scales.cpp:19:45: warning: declaration of 'vt' shadows a global declaration [-Wshadow]
   19 | int fnd(int i,int j,int k,int a,vector<int>&vt){
      |                                 ~~~~~~~~~~~~^~
scales.cpp:17:20: note: shadowed declaration is here
   17 | vector<vector<int>>vt[mxn];
      |                    ^~
scales.cpp: In function 'void build(int)':
scales.cpp:49:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 for(int idx=0;idx<vt[node].size();idx++){
      |                               ~~~^~~~~~~~~~~~~~~~
scales.cpp:72:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |                 for(int idx=0;idx<vt[node].size();idx++){
      |                               ~~~^~~~~~~~~~~~~~~~
scales.cpp:95:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                 for(int idx=0;idx<vt[node].size();idx++){
      |                               ~~~^~~~~~~~~~~~~~~~
scales.cpp:122:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |                     for(int idx=0;idx<vt[node].size();idx++){
      |                                   ~~~^~~~~~~~~~~~~~~~
scales.cpp:152:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         for(int idx=0;idx<vt[node].size();idx++){
      |                       ~~~^~~~~~~~~~~~~~~~
scales.cpp:165:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for(int idx=0;idx<vt[node].size();idx++){
      |                       ~~~^~~~~~~~~~~~~~~~
scales.cpp:178:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         for(int idx=0;idx<vt[node].size();idx++){
      |                       ~~~^~~~~~~~~~~~~~~~
scales.cpp:191:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         for(int idx=0;idx<vt[node].size();idx++){
      |                       ~~~^~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:244:15: warning: unused parameter 'T' [-Wunused-parameter]
  244 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:254:16: warning: declaration of 'vt' shadows a global declaration [-Wshadow]
  254 |     vector<int>vt=query(1);
      |                ^~
scales.cpp:17:20: note: shadowed declaration is here
   17 | vector<vector<int>>vt[mxn];
      |                    ^~
scales.cpp: In function 'void build(int)':
scales.cpp:153:72: warning: 'kx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |             if(vt[node][idx][ix]>max(vt[node][idx][jx],vt[node][idx][kx])){
      |                                                                        ^
scales.cpp:153:54: warning: 'jx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |             if(vt[node][idx][ix]>max(vt[node][idx][jx],vt[node][idx][kx])){
      |                                                      ^
scales.cpp:153:32: warning: 'ix' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |             if(vt[node][idx][ix]>max(vt[node][idx][jx],vt[node][idx][kx])){
      |                                ^

• Subtask 1: 71.428571 / 100