Submission #331321

#	Time	Username	Problem	Language	Result	Execution time	Memory
331321		IloveN	Scales (IOI15_scales)	C++14	0 / 100	530 ms	8320 KiB

scales

#include<bits/stdc++.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>
#include "scales.h"
const int N=1e3+10;
const int pw[]={1,3,9,27,81,243,729};
struct ds {int t,a,b,c,d;};
vi per[N];
int n,np,k=0,ans[N][N],pos[7];
ds opr[N];

bool cmp(int x,int y) { return pos[x]<pos[y];}

int query(ds &x)
{
    int t=x.t,a=x.a,b=x.b,c=x.c,d=x.d;
    if (t==1)
    {
        if (pos[a]<pos[b]) swap(a,b);
        if (pos[a]<pos[c]) swap(a,c);
        return a;
    }
    else if (t==2)
    {
        if (pos[a]>pos[b]) swap(a,b);
        if (pos[a]>pos[c]) swap(a,c);
        return a;
    }
    else if (t==3)
    {
        if (pos[a]>pos[b]) swap(a,b);
        if (pos[a]>pos[c]) swap(a,c);
        if (pos[b]>pos[c]) swap(b,c);
        return b;
    }
    vi vt,vt2;
    if (pos[a]>pos[d]) vt.eb(a);
    else vt2.eb(a);
    if (pos[b]>pos[d]) vt.eb(b);
    else vt2.eb(b);
    if (pos[c]>pos[d]) vt.eb(c);
    else vt2.eb(a);
    if (vt.empty()) vt=vt2;
    sort(all(vt));
    return vt[0];
}

void build()
{
    n=6;
    np=720;
    vi vt;
    for (int i=1;i<=n;i++) vt.eb(i);
    for (int i=1;i<=np;i++)
    {
        per[i]=vt;
        next_permutation(all(vt));
    }
    for (int t=1;t<=3;t++)
        for (int a=1;a<=n;a++)
            for (int b=a+1;b<=n;b++)
                for (int c=b+1;c<=n;c++) opr[++k]={t,a,b,c,0};
    for (int a=1;a<=n;a++)
        for (int b=a+1;b<=n;b++)
            for (int c=b+1;c<=n;c++)
                for (int d=1;d<=n;d++)
                    if (d!=a && d!=b && d!=c) opr[++k]={4,a,b,c,d};
    for (int i=1;i<=np;i++)
    {
        for (int j=0;j<6;j++) pos[per[i][j]]=j;
        for (int j=1;j<=k;j++)
            ans[i][j]=query(opr[j]);
    }
}

map<vi,int> mov;
bool solve(vi vt,int d)
{
    if (vt.size()<=1) return true;
    if ((int)vt.size()>pw[d]) return false;
    if (d==6) {
    for (int i=1;i<=61;i+=20)
    {
        vi typ[7];
        for (int x : vt) typ[ans[x][i]].eb(x);
        int check=1;
        for (int j=1;j<=6;j++)
            if (!solve(typ[j],d-1))
            {
                check=0;
                break;
            }
        if (check)
        {
            mov[vt]=i;
            return true;
        }
    } }
    else {
    for (int i=1;i<=k;i++)
    {
        vi typ[7];
        for (int x : vt) typ[ans[x][i]].eb(x);
        int check=1;
        for (int j=1;j<=6;j++)
            if (!solve(typ[j],d-1))
            {
                check=0;
                break;
            }
        if (check)
        {
            mov[vt]=i;
            return true;
        }
    } }
    return false;
}

void process()
{
    vi vt;
    for (int i=1;i<=np;i++) vt.eb(i);
    solve(vt,6);
    cout<<mov.size();
}

void init(int T)
{
    build();
    process();
}

int get_ans(ds x)
{
    int t=x.t,a=x.a,b=x.b,c=x.c,d=x.d;
    if (t==1) return getHeaviest(a,b,c);
    if (t==2) return getLightest(a,b,c);
    if (t==3) return getMedian(a,b,c);
    return getNextLightest(a,b,c,d);
}

void orderCoins()
{
    vi vt;
    for (int i=1;i<=np;i++) vt.eb(i);
    for (int i=1;i<=6;i++)
    {
        int d=mov[vt];
        int res=get_ans(opr[d]);
        vi vt2;
        for (int x : vt)
            if (ans[x][d]==res) vt2.eb(x);
        vt=vt2;
    }
    int x=vt[0];
    int W[] = {1, 2, 3, 4, 5, 6};
    for (int i=0;i<6;i++) W[i]=per[x][i];
    answer(W);
}

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

Compilation message (stderr)

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

• Subtask 1: 0 / 100