oj.uz

Submission #606353

# Submission time Handle Problem Language Result Execution time Memory
606353 2022-07-26T06:24:42 Z Koosha_mv Scales (IOI15_scales) C++14
73.2143 / 100
 165 ms 472 KB 
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=7;

int n=6,cnt[N];
vector<vector<int>> op,vc;

int Max(){
    int mx=0;
    f(i,0,N) maxm(mx,cnt[i]);
    return mx;
}
int getLightest(int A, int B, int C,vector<int> vec){
    int ted=0;
    for(auto x : vec){
        int id=-1;
        if(x==A){
            id=A;
        }
        if(x==B){
            id=B;
        }
        if(x==C){
            id=C;
        }
        if(id!=-1){
            ted++;
            if(ted==1) return id;
        }
    }
    return 0;
}
int getMedian(int A, int B, int C,vector<int> vec){
    vector<pair<int,int>> p;
    int ted=0;
    for(auto x : vec){
        int id=-1;
        if(x==A){
            id=A;
        }
        if(x==B){
            id=B;
        }
        if(x==C){
            id=C;
        }
        if(id!=-1){
            ted++;
            if(ted==2) return id;
        }
    }
    return 0;
}
int getHeaviest(int A, int B, int C,vector<int> vec){
    vector<pair<int,int>> p;
    int ted=0;
    for(auto x : vec){
        int id=-1;
        if(x==A){
            id=A;
        }
        if(x==B){
            id=B;
        }
        if(x==C){
            id=C;
        }
        if(id!=-1){
            ted++;
            if(ted==3) return id;
        }
    }
    return 0;
}
int getNextLightest(int A, int B, int C, int D,vector<int> vec){
    int b=0;
    for(auto x : vec){
        if(x==D) b=1;
        if(b==1 && (x==A || x==B || x==C)){
            return x;
        }
    }
    for(auto x : vec){
        if(b==1 && (x==A || x==B || x==C)){
            return x;
        }
    }
    return 0;
}
void do_it(){
    int res=int(vc.size());
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getLightest(p[0],p[1],p[2],v)]++;
        }
        minm(res,Max());
    }
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getMedian(p[0],p[1],p[2],v)]++;
        }
        minm(res,Max());
    }
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getHeaviest(p[0],p[1],p[2],v)]++;
        }
        minm(res,Max());
    }
    for(auto p : op){
        f(x,1,n+1){
            fill(cnt,cnt+N,0);
            if(x==p[0] || x==p[1] || x==p[2]) continue ;
            for(auto v : vc){
                cnt[getNextLightest(p[0],p[1],p[2],x,v)]++;
            } 
            minm(res,Max());
        }
    }

    //----------------------

    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getMedian(p[0],p[1],p[2],v)]++;
        }
        if(res==Max()){
            vector<vector<int>> nvc;
            int id=getMedian(p[0],p[1],p[2]);
            for(auto v : vc){
                if(getMedian(p[0],p[1],p[2],v)==id){
                    nvc.pb(v);
                }
            }
            vc=nvc;   
            return ;
        }
    }
    for(auto p : op){
        f(x,1,n+1){
            fill(cnt,cnt+N,0);
            if(x==p[0] || x==p[1] || x==p[2]) continue ;
            for(auto v : vc){
                cnt[getNextLightest(p[0],p[1],p[2],x,v)]++;
            } 
            if(Max()==res){
                vector<vector<int>> nvc;
                int id=getNextLightest(p[0],p[1],p[2],x);
                for(auto v : vc){
                    if(getNextLightest(p[0],p[1],p[2],x,v)==id){
                        nvc.pb(v);
                    }
                }
                vc=nvc;
                return ;
            }
        }
    }
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getLightest(p[0],p[1],p[2],v)]++;
        }
        if(res==Max()){
            vector<vector<int>> nvc;
            int id=getLightest(p[0],p[1],p[2]);
            for(auto v : vc){
                if(getLightest(p[0],p[1],p[2],v)==id){
                    nvc.pb(v);
                }
            }   
            vc=nvc;
            return ;
        }
    }
    for(auto p : op){
        fill(cnt,cnt+N,0);
        for(auto v : vc){
            cnt[getHeaviest(p[0],p[1],p[2],v)]++;
        }
        if(res==Max()){
            vector<vector<int>> nvc;
            int id=getHeaviest(p[0],p[1],p[2]);
            for(auto v : vc){
                if(getHeaviest(p[0],p[1],p[2],v)==id){
                    nvc.pb(v);
                }
            }   
            vc=nvc;
            return ;
        }
    }

}
void orderCoins() {
    op.clear();
    vc.clear();
    vector<int> p(n);   
    iota(all(p),1);
    do{
        vc.pb(p);
    } while(next_permutation(all(p)));
    f(i,0,n) p[i]=(i>=3);
    do{
        vector<int> v;
        f(i,0,n) if(p[i]==1) v.pb(i+1);
        op.pb(v);
    } while(next_permutation(all(p)));
    ////
    //vc.clear();
    //vc.pb({3,4,6,2,1,5});
    //vc.pb({3,4,6,2,5,1});
    ///

    while(vc.size()>1){
        do_it();
        //eror(vc.size());
    }
    //eror(vc.size());
    //cout<<"ans -> ";
    //for(auto x : vc[0]) cout<<x<<" ";
    //cout<<endl;
    int W[6];
    f(i,0,6) W[i]=vc[0][i];
    answer(W);
}
void init(int T) {
    T=T;
}

/*int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);
*/

Subtask #1
73.214286 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 160 ms 344 KB Output is partially correct
2 Partially correct 146 ms 348 KB Output is partially correct
3 Partially correct 154 ms 340 KB Output is partially correct
4 Partially correct 156 ms 340 KB Output is partially correct
5 Partially correct 141 ms 340 KB Output is partially correct
6 Correct 141 ms 340 KB Output is correct
7 Partially correct 162 ms 340 KB Output is partially correct
8 Partially correct 144 ms 340 KB Output is partially correct
9 Partially correct 142 ms 348 KB Output is partially correct
10 Partially correct 143 ms 344 KB Output is partially correct
11 Partially correct 143 ms 340 KB Output is partially correct
12 Partially correct 140 ms 344 KB Output is partially correct
13 Partially correct 146 ms 460 KB Output is partially correct
14 Partially correct 145 ms 344 KB Output is partially correct
15 Partially correct 148 ms 340 KB Output is partially correct
16 Correct 140 ms 340 KB Output is correct
17 Partially correct 148 ms 468 KB Output is partially correct
18 Correct 156 ms 340 KB Output is correct
19 Partially correct 147 ms 352 KB Output is partially correct
20 Partially correct 142 ms 340 KB Output is partially correct
21 Correct 146 ms 340 KB Output is correct
22 Partially correct 144 ms 344 KB Output is partially correct
23 Partially correct 141 ms 472 KB Output is partially correct
24 Partially correct 145 ms 340 KB Output is partially correct
25 Partially correct 149 ms 344 KB Output is partially correct
26 Partially correct 142 ms 364 KB Output is partially correct
27 Partially correct 145 ms 340 KB Output is partially correct
28 Partially correct 144 ms 340 KB Output is partially correct
29 Partially correct 149 ms 340 KB Output is partially correct
30 Correct 147 ms 352 KB Output is correct
31 Partially correct 143 ms 340 KB Output is partially correct
32 Partially correct 140 ms 340 KB Output is partially correct
33 Correct 145 ms 468 KB Output is correct
34 Partially correct 142 ms 340 KB Output is partially correct
35 Partially correct 141 ms 340 KB Output is partially correct
36 Partially correct 165 ms 340 KB Output is partially correct
37 Partially correct 144 ms 344 KB Output is partially correct
38 Partially correct 139 ms 340 KB Output is partially correct
39 Partially correct 142 ms 348 KB Output is partially correct
40 Partially correct 142 ms 364 KB Output is partially correct