Submission #109882

#	Time	Username	Problem	Language	Result	Execution time	Memory
109882		boatinw99	Mechanical Doll (IOI18_doll)	C++11	100 / 100	153 ms	14848 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
using namespace std ;
typedef pair<int,int> pii ;
#define fi first
#define se second
const int N = 2e5+9 ;
#define mid (l+r>>1)
vector<pii> pos ;
int n,L[N<<4],R[N<<4],id=1,a[N<<1],f[N<<1];
int construct(int l,int r,int x,int m)
{
    if(r<x)
    {
        id--;
        return -1 ;
    }
    if(l==r)
    {
        id--;
        return a[l];
    }
    L[m]=construct(l,mid,x,++id);
    R[m]=construct(mid+1,r,x,++id);
    return -m ;
}
void create_circuit(int M, vector<int> A)
{
    n=A.size()+1;
    A.push_back(0);
    int sz ;
    for(sz=1;sz<n;sz<<=1);
    f[1]=1;
    for(int len=sz/2,idx=1;len;len/=2,idx*=2)
    {
        for(int j=1;j<=idx;j++)f[j+idx]=f[j]+len ;
    }
    for(int i=sz-n+1;i<=sz;i++)pos.push_back({f[i],i});
    sort(pos.begin(),pos.end());
    int ptr = 0 ;
    for(auto it:pos)a[it.se]=A[ptr++];
    construct(1,sz,sz-n+1,1);
    vector<int> X(id),Y(id),C(M+1);
    for(int i=0;i<=M;i++)C[i]=-1;
    for(int i=1;i<=id;i++)
    {
        X[i-1]=L[i];
        Y[i-1]=R[i];
    }
    answer(C,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'int construct(int, int, int, int)':
doll.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 | #define mid (l+r>>1)
      |              ~^~
doll.cpp:23:22: note: in expansion of macro 'mid'
   23 |     L[m]=construct(l,mid,x,++id);
      |                      ^~~
doll.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    8 | #define mid (l+r>>1)
      |              ~^~
doll.cpp:24:20: note: in expansion of macro 'mid'
   24 |     R[m]=construct(mid+1,r,x,++id);
      |                    ^~~

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