Submission #379290

#	Time	Username	Problem	Language	Result	Execution time	Memory
379290		IloveN	Scales (IOI15_scales)	C++14	100 / 100	493 ms	4952 KiB

scales

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

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=1e3+10,max_depth=6;
struct query
{
    int tp,a,b,c,d;
};

vi permu[N];
query Q[N];
int q=0,pos[N],pw3[N];

int heavy(int a,int b,int c)
{
    if (pos[b]>pos[a]) swap(a,b);
    if (pos[c]>pos[a]) return c;
    return a;
}

int light(int a,int b,int c)
{
    if (pos[b]<pos[a]) swap(a,b);
    if (pos[c]<pos[a]) return c;
    return a;
}

int med(int a,int b,int c)
{
    if (pos[b]>pos[a]) swap(a,b);
    if (pos[c]>pos[a]) swap(a,c);
    if (pos[b]>pos[c]) return b;
    return c;
}

int next_light(int a,int b,int c,int d)
{
    int mn=10,res;
    if (pos[a]>pos[d] && pos[a]<mn) mn=pos[a],res=a;
    if (pos[b]>pos[d] && pos[b]<mn) mn=pos[b],res=b;
    if (pos[c]>pos[d] && pos[c]<mn) mn=pos[c],res=c;
    if (mn!=10) return res;
    return light(a,b,c);
}

int ans[N][N];
map<vi,int> choose;

bool solve(vi &vt,int depth)
{
    if ((int)vt.size()>pw3[depth]) return false;
    if ((int)vt.size()<=1) return true;
    if (depth==max_depth)
    {
        vi cq={1,21,41,61};
        for (int i : cq)
        {
            vi nxvt[7];
            for (int x : vt) nxvt[ans[x][i]].eb(x);
            int check=1;
            for (int j=1;j<=6;j++)
                if (!nxvt[j].empty())
                {
                    if (!solve(nxvt[j],depth-1))
                    {
                        check=0;
                        break;
                    }
                }
            if (check)
            {
                choose[vt]=i;
                return true;
            }
        }
        return false;
    }
    for (int i=1;i<=q;i++)
    {
        vi nxvt[7];
        for (int x : vt) nxvt[ans[x][i]].eb(x);
        int check=1;
        for (int j=1;j<=6;j++)
            if (!nxvt[j].empty())
            {
                if (!solve(nxvt[j],depth-1))
                {
                    check=0;
                    break;
                }
            }
        if (check)
        {
            choose[vt]=i;
            return true;
        }
    }
    return false;
}

void precal()
{
    vi vt;
    for (int i=1;i<=6;i++) vt.eb(i);
    for (int i=1;i<=720;i++)
    {
        permu[i]=vt;
        next_permutation(all(vt));
    }
    for (int tp=1;tp<=3;tp++)
        for (int a=1;a<=6;a++)
            for (int b=a+1;b<=6;b++)
                for (int c=b+1;c<=6;c++) Q[++q]={tp,a,b,c,0};
    for (int a=1;a<=6;a++)
        for (int b=a+1;b<=6;b++)
            for (int c=b+1;c<=6;c++)
                for (int d=1;d<=6;d++)
                    if (d!=a && d!=b && d!=c) Q[++q]={4,a,b,c,d};
    for (int i=1;i<=720;i++)
    {
        for (int j=0;j<6;j++) pos[permu[i][j]]=j;
        for (int j=1;j<=q;j++)
        {
            int tp=Q[j].tp,a=Q[j].a,b=Q[j].b,c=Q[j].c,d=Q[j].d;
            if (tp==1) ans[i][j]=heavy(a,b,c);
            else if (tp==2) ans[i][j]=light(a,b,c);
            else if (tp==3) ans[i][j]=med(a,b,c);
            else ans[i][j]=next_light(a,b,c,d);
        }
    }
    pw3[0]=1;
    for (int i=1;i<=max_depth;i++) pw3[i]=pw3[i-1]*3;
    vt.clear();
    for (int i=1;i<=720;i++) vt.eb(i);
    solve(vt,max_depth);
}

int ask(int id)
{
    int tp=Q[id].tp,a=Q[id].a,b=Q[id].b,c=Q[id].c,d=Q[id].d;
    if (tp==1) return getHeaviest(a,b,c);
    if (tp==2) return getLightest(a,b,c);
    if (tp==3) return getMedian(a,b,c);
    return getNextLightest(a,b,c,d);
}

void init(int T)
{
    precal();
}

void orderCoins()
{
    vi vt;
    for (int i=1;i<=720;i++) vt.eb(i);
    while (vt.size()>1)
    {
        int id=choose[vt];
        int d=ask(id);
        vi vt2;
        for (int x : vt)
            if (ans[x][id]==d) vt2.eb(x);
        vt=vt2;
    }
    int W[6];
    for (int i=0;i<6;i++) W[i]=permu[vt[0]][i];
    answer(W);
}

/*int main()
{
    //freopen("ss.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    precal();
    return 0;
}*/

Compilation message (stderr)

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

• Subtask 1: 100 / 100