Submission #827578

#	Time	Username	Problem	Language	Result	Execution time	Memory
827578		Supersonic	Scales (IOI15_scales)	C++14	46.82 / 100	149 ms	312 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
set<int> gt[7];
set<int> lt[7];
set<int> gtbk[7];
set<int> ltbk[7];
int score(){
    int sc=0;
    for(int i=1;i<=6;i++){
        sc+=(int)(gt[i].size()+lt[i].size());
    }
    //cerr<<sc<<endl;
    return sc;
}
void backup(){
    for(int i=1;i<=6;i++){
        gtbk[i]=gt[i];
        ltbk[i]=lt[i];
    }
}
void restore(){
    for(int i=1;i<=6;i++){
        gt[i]=gtbk[i];
        lt[i]=ltbk[i];
    }
}
void clean(){
    for(int i=1;i<=6;i++){
        gt[i].clear();
        lt[i].clear();
    }
    backup();
}

void dbg(){
    for(int i=1;i<=6;i++){
        cerr<<i<<" is greater than ";for(auto j:gt[i])cerr<<j<<' ';cerr<<endl;
    }cerr<<endl;

    for(int i=1;i<=6;i++){
        cerr<<i<<" is less than ";for(auto j:lt[i])cerr<<j<<' ';cerr<<endl;
    }cerr<<endl;
}

vector<int> done(){
    //dbg();
    vector<pair<int,int>> ix;
    bool chk[6]={0,0,0,0,0,0};
    for(int i=1;i<=6;i++){
        ix.push_back({lt[i].size(),i});
        chk[lt[i].size()]=1;
    }
    if(!(chk[0]&&chk[1]&&chk[2]&&chk[3]&&chk[4]&&chk[5]))return {-1};
    sort(ix.rbegin(),ix.rend());
    vector<int> r;
    for(auto i:ix)r.push_back(i.second);
    return r;
}

void update(int a,int b){
    if(a==b)return;
    //cerr<<a<<' '<<b<<endl;
    gt[b].insert(a);
    lt[a].insert(b);
    for(auto i:gt[a]){gt[b].insert(i);lt[i].insert(b);}
    for(auto i:lt[b]){lt[a].insert(i);gt[i].insert(a);}

    //for(int i=1;i<=6;i++)cerr<<gt[i].size()<<' ';cerr<<endl;
}
void init(int T) {
    T++;
}

void orderCoins() {
    clean();
    while(true){
        // lightest = 1, heaviest = 2
        vector<int> bop;int bopt=-1;int bc=-1;
        
        // lightest
        for(int a=1;a<=6;a++)for(int b=1;b<=6;b++)for(int c=1;c<=6;c++){
            if(a==b||a==c||b==c)continue;
            int e=1000000;
            backup();update(a,b);update(a,c);e=min(e,score());restore();
            backup();update(b,a);update(b,c);e=min(e,score());restore();
            backup();update(c,a);update(c,b);e=min(e,score());restore();
            if(e>bc){bc=e;bopt=1;bop={a,b,c};}
        }

        for(int a=1;a<=6;a++)for(int b=1;b<=6;b++)for(int c=1;c<=6;c++){
            if(a==b||a==c||b==c)continue;
            int e=1000000;
            backup();update(b,a);update(c,a);e=min(e,score());restore();
            backup();update(a,b);update(c,b);e=min(e,score());restore();
            backup();update(a,c);update(b,c);e=min(e,score());restore();
            if(e>bc){bc=e;bopt=2;bop={a,b,c};}
        }
        for(int a=1;a<=6;a++)for(int b=1;b<=6;b++)for(int c=1;c<=6;c++){
            if(a==b||a==c||b==c)continue;
            int e=1000000;
            backup();
            if(gt[a].count(b)){update(a,c);}
            else if(gt[a].count(c)){update(a,b);}
            e=min(e,score());restore();
            backup();
            if(gt[b].count(a)){update(b,c);}
            else if(gt[b].count(c)){update(b,a);}
            e=min(e,score());restore();
            backup();
            if(gt[c].count(a)){update(c,b);}
            else if(gt[c].count(b)){update(c,a);}
            e=min(e,score());restore();
            if(e>bc){bc=e;bopt=3;bop={a,b,c};}
        }
        for(int a=1;a<=6;a++)for(int b=1;b<=6;b++)for(int c=1;c<=6;c++)for(int d=1;d<=6;d++){
            if(a==b||a==c||a==d||b==c||b==d||c==d)continue;
            if(!(gt[a].count(d)||gt[b].count(d)||gt[c].count(d)))continue;
            int e=1000000;
            backup();
            /*c
            d<c 
            a<c -> a<d
            a>d -> a>c*/
            update(d,a);
            if(lt[b].count(a))update(b,d);
            if(gt[b].count(d))update(a,b);
            if(lt[c].count(a))update(c,d);
            if(gt[c].count(d))update(a,c);
            e=min(e,score());restore();

            backup();
            update(d,b);
            if(lt[a].count(b))update(a,d);
            if(gt[a].count(d))update(b,a);
            if(lt[c].count(b))update(c,d);
            if(gt[c].count(d))update(b,c);
            e=min(e,score());restore();

            backup();
            update(d,c);
            if(lt[a].count(c))update(a,d);
            if(gt[a].count(d))update(c,a);
            if(lt[b].count(c))update(b,d);
            if(gt[b].count(d))update(c,b);
            e=min(e,score());restore();

            if(e>bc){bc=e;bopt=4;bop={a,b,c,d};}
        }
        if(bopt==-1){cerr<<"ERROR"<<endl;exit(1);}
        if(bopt==1){
            //cerr<<"LIGHT: "<<bop[0]<<' '<<bop[1]<<' '<<bop[2]<<endl;
            //cerr<<bc<<endl;
            int r=getLightest(bop[0],bop[1],bop[2]);
            update(r,bop[0]);update(r,bop[1]);update(r,bop[2]);
        }
        if(bopt==2){
            //cerr<<"HEAVY: "<<bop[0]<<' '<<bop[1]<<' '<<bop[2]<<endl;
            //cerr<<bc<<endl;
            int r=getHeaviest(bop[0],bop[1],bop[2]);
            update(bop[0],r);update(bop[1],r);update(bop[2],r);
        }
        if(bopt==3){
            //cerr<<"MEDIAN: "<<bop[0]<<' '<<bop[1]<<' '<<bop[2]<<endl;
            int r=getMedian(bop[0],bop[1],bop[2]);
            if(r==bop[0]){
                if(gt[bop[0]].count(bop[1])){update(bop[0],bop[2]);}
                else if(gt[bop[0]].count(bop[2])){update(bop[0],bop[1]);}
            }
            if(r==bop[1]){
                if(gt[bop[1]].count(bop[0])){update(bop[1],bop[2]);}
                else if(gt[bop[1]].count(bop[2])){update(bop[1],bop[0]);}
            }
            if(r==bop[2]){
                if(gt[bop[2]].count(bop[0])){update(bop[2],bop[1]);}
                else if(gt[bop[2]].count(bop[1])){update(bop[2],bop[0]);}
            }
        }
        if(bopt==4){
            //cerr<<"NL: "<<bop[0]<<' '<<bop[1]<<' '<<bop[2]<<'-'<<bop[3]<<endl;
            int r=getNextLightest(bop[0],bop[1],bop[2],bop[3]);
            cerr<<r<<endl;
            if(r==bop[0]){
            update(bop[3],bop[0]);
            if(lt[bop[1]].count(bop[0]))update(bop[1],bop[3]);
            if(gt[bop[1]].count(bop[3]))update(bop[0],bop[1]);
            if(lt[bop[2]].count(bop[0]))update(bop[2],bop[3]);
            if(gt[bop[2]].count(bop[3]))update(bop[0],bop[2]);}
            if(r==bop[1]){
            update(bop[3],bop[1]);
            if(lt[bop[0]].count(bop[1]))update(bop[0],bop[3]);
            if(gt[bop[0]].count(bop[3]))update(bop[1],bop[0]);
            if(lt[bop[2]].count(bop[1]))update(bop[2],bop[3]);
            if(gt[bop[2]].count(bop[3]))update(bop[1],bop[2]);}
            if(r==bop[2]){
            update(bop[3],bop[2]);
            if(lt[bop[0]].count(bop[2]))update(bop[0],bop[3]);
            if(gt[bop[0]].count(bop[3]))update(bop[2],bop[0]);
            if(lt[bop[1]].count(bop[2]))update(bop[1],bop[3]);
            if(gt[bop[1]].count(bop[3]))update(bop[2],bop[1]);}
        }
        vector<int> rr=done();
        if(rr[0]>0){
            int ra[6]={rr[0],rr[1],rr[2],rr[3],rr[4],rr[5]};
            answer(ra);
            return;
        }
        //else clean();
    }
    
}

• Subtask 1: 46.818182 / 100