Submission #705252

#	Time	Username	Problem	Language	Result	Execution time	Memory
705252		bin9638	Scales (IOI15_scales)	C++17	10.81 / 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];
}
#endif // SKY

struct trip
{
    int A,B,C;
};
vector<trip>trip;
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();
        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
    srand(time(0));
    for(int i=1;i<=6;i++)
        g[i].clear();
    trip.clear();
    for(int i=1;i<=6;i++)
        for(int j=1;j<i;j++)
            for(int k=1;k<j;k++)
                trip.pb({i,j,k});
    random_shuffle(trip.begin(),trip.end());
    for(auto u:trip)
    {
        int c=getHeaviest(u.A,u.B,u.C);
        if(c!=u.A)
            g[u.A].pb(c);
        if(c!=u.B)
            g[u.B].pb(c);
        if(c!=u.C)
            g[u.C].pb(c);
        if(check())
        {
            int kq[6];
            for(int i=1;i<=6;i++)
                kq[__builtin_popcount(bit[i])-1]=i;
            answer(kq);
            return;
        }
        c=getLightest(u.A,u.B,u.C);
        if(c!=u.A)
            g[c].pb(u.A);
        if(c!=u.B)
            g[c].pb(u.B);
        if(c!=u.C)
            g[c].pb(u.C);
        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 orderCoins()':
scales.cpp:91:15: warning: conversion from 'time_t' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
   91 |     srand(time(0));
      |           ~~~~^~~
scales.cpp: In function 'void init(int)':
scales.cpp:135:15: warning: unused parameter 'q' [-Wunused-parameter]
  135 | void init(int q)
      |           ~~~~^

• Subtask 1: 10.813822 / 100