Submission #101694

#	Time	Username	Problem	Language	Result	Execution time	Memory
101694		HNO2	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	332 KiB

doll

#include <bits/stdc++.h>
#include <doll.h>
using namespace std;

typedef long long ll;
const int maxn=1e6+7;
const int inf=INT_MAX;
const ll inff=1e18;
const ll mod=1e9+7;
#define pii pair<int,int>
#define mkp make_pair
#define F first
#define S second
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//#define int ll
//#define endl '\n'

int state[maxn],out[maxn];
int ansx[maxn],ansy[maxn],ansc[maxn],used[maxn];
int now=1,cnt=0;
vector<int> appear;
vector<int> c,x,y;
map<int,int> mp;

void create_circuit(int m,vector<int> a)
{
    int n=sz(a);
    while (now<n) now*=2,cnt++;
    now/=2;
    for (int i=1;i<now*2;i++)
    {
        int N=1;
        for (int j=1;j<=cnt;j++)
        {
            if (state[N]==0) state[N]=1,N=2*N;
            else state[N]=0,N=2*N+1;
        }
        appear.pb(N);
    }
    int tmp=0;
    for (int i:appear)
    {
        if (i<=now+n&&i!=appear.back()&&tmp<n)
        {
            out[i]=a[tmp++];
        }
        else if (i==appear.back())
        {
            out[i]=0;
        }
        else
        {
            out[i]=-1;
        }
    }
    for (int i=now;i<2*now;i++)
    {
        if (!(i&1))
        {
            ansx[i/2]=out[i];
        }
        else
        {
            ansy[(i-1)/2]=out[i];
        }
    }
    int ttmp=-1;
    for (int i=1;i<=now-1;i++)
    {
        ansx[i]=2*i;
        if (ansx[ansx[i]]==-1&&ansy[ansx[i]]==-1) used[ansx[i]]=1,ansx[i]=-1;
        ansy[i]=2*i+1;
        if (ansx[ansy[i]]==-1&&ansy[ansy[i]]==-1) used[ansy[i]]=1,ansy[i]=-1;
    }
    for (int i=0;i<=m;i++) c.pb(-1);
    for (int i=1;i<now*2;i++)
    {
        if (!used[i])
        {
            mp[i]=ttmp;
            ttmp--;
        }
    }
    mp[-1]=-1;
    mp[0]=0;
    for (int i=1;i<now*2;i++)
    {
        if (!used[i])
        {
            x.pb(mp[ansx[i]]);
            y.pb(mp[ansy[i]]);
        }
    }
    answer(c,x,y);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56