Submission #584822

#	Time	Username	Problem	Language	Result	Execution time	Memory
584822		krit3379	Scales (IOI15_scales)	C++17	72.92 / 100	138 ms	468 KiB

scales

#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
#define N 100005
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

struct A{
    int id,i,j,k,l;
}upd;

vector<vector<int>> per;
vector<int> v;

void init(int t){
    v={0,1,2,3,4,5};
    do{
        per.push_back(v);
    }while(next_permutation(v.begin(),v.end()));
}

void orderCoins(){
    int ma,m,m1,m2,i,j,k,l,a,b,c,d,c1,c2,c3,x;
    int ans[6];
    vector<vector<int>> now=per,temp;
    while(now.size()>1){
        ma=2e9;
        //case 1
        for(i=0;i<6;i++)for(j=i+1;j<6;j++)for(k=j+1;k<6;k++){
            c1=c2=c3=0;
            for(auto arr:now){
                a=arr[i],b=arr[j],c=arr[k];
                m=max({a,b,c});
                if(m==a)c1++;
                else if(m==b)c2++;
                else c3++;
            }
            if(max({c1,c2,c3})<=ma)ma=max({c1,c2,c3}),upd={1,i,j,k};
        }
        //case 2
        for(i=0;i<6;i++)for(j=i+1;j<6;j++)for(k=j+1;k<6;k++){
            c1=c2=c3=0;
            for(auto arr:now){
                a=arr[i],b=arr[j],c=arr[k];
                m=min({a,b,c});
                if(m==a)c1++;
                else if(m==b)c2++;
                else c3++;
            }
            if(max({c1,c2,c3})<=ma)ma=max({c1,c2,c3}),upd={2,i,j,k};
        }
        //case 3
        for(i=0;i<6;i++)for(j=i+1;j<6;j++)for(k=j+1;k<6;k++){
            c1=c2=c3=0;
            for(auto arr:now){
                a=arr[i],b=arr[j],c=arr[k];
                m1=min({a,b,c});
                m2=max({a,b,c});
                if(a!=m1&&a!=m2)c1++;
                else if(b!=m1&&b!=m2)c2++;
                else c3++;
            }
            if(max({c1,c2,c3})<=ma)ma=max({c1,c2,c3}),upd={3,i,j,k};
        }
        //case 4
        for(i=0;i<6;i++)for(j=i+1;j<6;j++)for(k=j+1;k<6;k++)for(l=0;l<6;l++){
            if(l==i||l==j||l==k)continue;
            c1=c2=c3=0;
            for(auto arr:now){
                a=arr[i],b=arr[j],c=arr[k],d=arr[l];
                vector<int> t={a,b,c};
                sort(t.begin(),t.end());
                if(arr[l]>t[2]||arr[l]<t[0]){
                    if(a==t[0])c1++;
                    else if(b==t[0])c2++;
                    else c3++;
                }
                else if(arr[l]<t[1]){
                    if(a==t[1])c1++;
                    else if(b==t[1])c2++;
                    else c3++;
                }
                else{
                    if(a==t[2])c1++;
                    else if(b==t[2])c2++;
                    else c3++;
                }
            }
            if(max({c1,c2,c3})<=ma)ma=max({c1,c2,c3}),upd={4,i,j,k,l};
        }
        auto [op,i,j,k,l]=upd;
        if(op==1){
            x=getHeaviest(i+1,j+1,k+1);
            x--;
            for(auto arr:now)if(arr[x]==max({arr[i],arr[j],arr[k]}))temp.push_back(arr);
        }
        else if(op==2){
            x=getLightest(i+1,j+1,k+1);
            x--;
            for(auto arr:now)if(arr[x]==min({arr[i],arr[j],arr[k]}))temp.push_back(arr);
        }
        else if(op==3){
            x=getMedian(i+1,j+1,k+1);
            x--;
            for(auto arr:now)if(arr[x]!=max({arr[i],arr[j],arr[k]})&&arr[x]!=min({arr[i],arr[j],arr[k]}))temp.push_back(arr);
        }
        else{
            x=getNextLightest(i+1,j+1,k+1,l+1);
            x--;
            int sz=0;
            for(auto arr:now){
                int t=1e9;
                if(arr[i]>arr[l])t=min(t,arr[i]);
                if(arr[j]>arr[l])t=min(t,arr[j]);
                if(arr[k]>arr[l])t=min(t,arr[k]);
                if((max({arr[i],arr[j],arr[k]})<arr[l]&&arr[x]==min({arr[i],arr[j],arr[k]}))||arr[x]==t)temp.push_back(arr);
            }
        }
        now=temp;
        temp.clear();
    }
    for(i=0;i<6;i++)ans[now[0][i]]=i+1;
    answer(ans);
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:15:15: warning: unused parameter 't' [-Wunused-parameter]
   15 | void init(int t){
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:38:67: warning: missing initializer for member 'A::l' [-Wmissing-field-initializers]
   38 |             if(max({c1,c2,c3})<=ma)ma=max({c1,c2,c3}),upd={1,i,j,k};
      |                                                                   ^
scales.cpp:50:67: warning: missing initializer for member 'A::l' [-Wmissing-field-initializers]
   50 |             if(max({c1,c2,c3})<=ma)ma=max({c1,c2,c3}),upd={2,i,j,k};
      |                                                                   ^
scales.cpp:63:67: warning: missing initializer for member 'A::l' [-Wmissing-field-initializers]
   63 |             if(max({c1,c2,c3})<=ma)ma=max({c1,c2,c3}),upd={3,i,j,k};
      |                                                                   ^
scales.cpp:91:18: warning: declaration of 'i' shadows a previous local [-Wshadow]
   91 |         auto [op,i,j,k,l]=upd;
      |                  ^
scales.cpp:23:20: note: shadowed declaration is here
   23 |     int ma,m,m1,m2,i,j,k,l,a,b,c,d,c1,c2,c3,x;
      |                    ^
scales.cpp:91:20: warning: declaration of 'j' shadows a previous local [-Wshadow]
   91 |         auto [op,i,j,k,l]=upd;
      |                    ^
scales.cpp:23:22: note: shadowed declaration is here
   23 |     int ma,m,m1,m2,i,j,k,l,a,b,c,d,c1,c2,c3,x;
      |                      ^
scales.cpp:91:22: warning: declaration of 'k' shadows a previous local [-Wshadow]
   91 |         auto [op,i,j,k,l]=upd;
      |                      ^
scales.cpp:23:24: note: shadowed declaration is here
   23 |     int ma,m,m1,m2,i,j,k,l,a,b,c,d,c1,c2,c3,x;
      |                        ^
scales.cpp:91:24: warning: declaration of 'l' shadows a previous local [-Wshadow]
   91 |         auto [op,i,j,k,l]=upd;
      |                        ^
scales.cpp:23:26: note: shadowed declaration is here
   23 |     int ma,m,m1,m2,i,j,k,l,a,b,c,d,c1,c2,c3,x;
      |                          ^
scales.cpp:110:17: warning: unused variable 'sz' [-Wunused-variable]
  110 |             int sz=0;
      |                 ^~
scales.cpp:23:34: warning: variable 'd' set but not used [-Wunused-but-set-variable]
   23 |     int ma,m,m1,m2,i,j,k,l,a,b,c,d,c1,c2,c3,x;
      |                                  ^

• Subtask 1: 72.916667 / 100