Submission #363959

#	Time	Username	Problem	Language	Result	Execution time	Memory
363959		Fysty	Mechanical Doll (IOI18_doll)	C++17	100 / 100	200 ms	14964 KiB

doll

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(0);cin.tie(0);
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define F first
#define S second
#define pb push_back
//#define int ll
const int MOD=1e9+7;
const ll INF=1e16;
const int N=100005;
const int maxN=1e6;
vector<int> ed[N];
ll t=0,x[maxN],y[maxN],out[maxN],c[N],root,rev[maxN];
void get_switch(int cnt,int l,int par,int k)
{
    int mid=k/2;
    if(k==2)
    {
        if(cnt==2)
        {
            out[l]=par;
            out[l+1]=par;
        }
        else
        {
            x[-par]=root;
            out[l+1]=par;
        }
        return;
    }
    if(cnt>mid)
    {
        t--;
        x[-par]=t;
        get_switch(cnt-mid,l,t,mid);
        t--;
        y[-par]=t;
        get_switch(mid,l+mid,t,mid);
    }
    else
    {
        x[-par]=root;
        t--;
        y[-par]=t;
        get_switch(cnt,l+mid,t,mid);
    }
}
void answer(vector<int> c,vector<int> x,vector<int> y);
void create_circuit(int M,vector<int> A)
{
    vector<int> c(M+1,-1),X,Y;
    A.pb(0);
    ll n=A.size();
    ll k=1,cnt=0;
    while(k<n) k<<=1,cnt++;
    t=root=-1;
    get_switch(A.size(),0,-1,k);
    ll cur=0;
    rep(i,k)
    {
        ll tmp=0,a=i;
        rep(j,cnt)
        {
            if(i&(1<<j)) tmp|=(1<<cnt-1-j);
        }
        if(out[tmp]!=0)
        {
            if(x[-out[tmp]]!=0) y[-out[tmp]]=A[cur];
            else x[-out[tmp]]=A[cur];
            cur++;
        }
    }
    rep(i,-t) X.pb(x[i+1]),Y.pb(y[i+1]);
    //rep(i,c.size()) cout<<i<<": "<<c[i]<<"\n";
    //rep(i,X.size()) cout<<-(i+1)<<": "<<X[i]<<" "<<Y[i]<<"\n";
    answer(c,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:68:40: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   68 |             if(i&(1<<j)) tmp|=(1<<cnt-1-j);
      |                                   ~~~~~^~
doll.cpp:65:18: warning: unused variable 'a' [-Wunused-variable]
   65 |         ll tmp=0,a=i;
      |                  ^

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