Submission #705270

#	Time	Username	Problem	Language	Result	Execution time	Memory
705270		bin9638	Scales (IOI15_scales)	C++17	55.56 / 100	1 ms	212 KiB

scales

#include <bits/stdc++.h>
#ifndef SKY
#include "scales.h"
#endif

using namespace std;

#define ll long long
#define fs first
#define sc second
#define N 12
#define pb push_back
#define ii pair<int,int>

int p[N],w[N];
vector<int>g[N];

#ifdef SKY
void answer(int W[])
{
    for(int i=0;i<6;i++)cout<<W[i]<<" ";cout<<endl;
}

bool SS(const int&u,const int&v)
{
    return w[u]<w[v];
}

int getHeaviest(int A, int B, int C)
{
   // cout<<"cc\n";
    int f[3]={A,B,C};
    sort(f,f+3,SS);
    return f[2];
}

int getLightest(int A,int B,int C)
{
    //cout<<"cc\n";
    int f[3]={A,B,C};
    sort(f,f+3,SS);
    return f[0];
}

int getNextLightest(int A, int B, int C, int D)
{
    //cout<<"cc\n";
    int f[3]={A,B,C};
    sort(f,f+3,SS);
    if(w[f[0]]>w[D])
        return f[0];
    if(w[f[1]]>w[D])
        return f[1];
    if(w[f[2]]>w[D])
        return f[2];
    return f[0];
}
#endif // SKY

int bit[N];

bool check()
{
    for(int i=1;i<=6;i++)
        bit[i]=(1<<i);
    int deg[N]={};
    stack<int>st;
    for(int i=1;i<=6;i++)
        for(auto v:g[i])
            deg[v]++;
    for(int i=1;i<=6;i++)
        if(deg[i]==0)
            st.push(i);
    while(!st.empty())
    {
        int u=st.top();
        //cout<<u<<" "<<bit[u]<<endl;
        st.pop();
        for(auto v:g[u])
        {
            bit[v]|=bit[u];
            if(--deg[v]==0)
                st.push(v);
        }
    }
    int ktr[N]={};
    for(int i=1;i<=6;i++)
        ktr[__builtin_popcount(bit[i])]++;
    for(int i=1;i<=6;i++)
        if(ktr[i]!=1)
            return 0;
    return 1;
}

void orderCoins()
{
    #ifdef SKY
    for(int i=1;i<=6;i++)
        cin>>p[i],w[p[i]]=i;
    #endif // SKY
    for(int i=1;i<=6;i++)
        g[i].clear();
    vector<int>L,R;
    int min_val=getLightest(1,2,3),max_val=getHeaviest(1,2,3);
    L.pb(min_val);
    L.pb(1+2+3-min_val-max_val);
    L.pb(max_val);
    min_val=getLightest(4,5,6);
    max_val=getHeaviest(4,5,6);
    R.pb(min_val);
    R.pb(4+5+6-min_val-max_val);
    R.pb(max_val);
    //for(auto u:L)cout<<u<<" ";cout<<endl;for(auto u:R)cout<<u<<" ";cout<<endl;
    g[L[0]].pb(L[1]);
    g[L[1]].pb(L[2]);
    g[R[0]].pb(R[1]);
    g[R[1]].pb(R[2]);
    if(getHeaviest(L[2],R[2],L[1])==R[2])
        swap(L,R);
    //for(auto u:L)cout<<u<<" ";cout<<endl;for(auto u:R)cout<<u<<" ";cout<<endl;
    for(auto u:R)
    {
        int c=getNextLightest(L[0],L[1],L[2],u);
       // cout<<u<<" "<<c<<endl;
        if(c==L[0])
            g[u].pb(L[0]);
        if(c==L[1])
        {
            g[u].pb(L[1]);
            g[L[0]].pb(u);
        }
        if(c==L[2])
        {
            g[u].pb(L[2]);
            g[L[1]].pb(u);
        }
    }
    if(check())
    {
        int kq[6];
        for(int i=1;i<=6;i++)
            kq[__builtin_popcount(bit[i])-1]=i;
        answer(kq);
        return;
    }
}

void init(int q)
{
    #ifdef SKY
    while(q--)
        orderCoins();
    #endif // SKY
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
  //  ios::sync_with_stdio(0);
   // cin.tie(NULL);
   // cout.tie(NULL);
    int q;
    cin>>q;
    init(q);
    return 0;
}
#endif // SKY

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:148:15: warning: unused parameter 'q' [-Wunused-parameter]
  148 | void init(int q)
      |           ~~~~^

• Subtask 1: 55.555556 / 100