Submission #1039464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039464		boyliguanhan	Mechanical Doll (IOI18_doll)	C++17	100 / 100	62 ms	11104 KiB

doll

#include "doll.h"
using namespace std;
int unneeded,CC,mp[1<<18];
vector<int>a,b;
int create(int l,int r){
    if(unneeded>r-l)
        return unneeded-=r-l+1,-1;
    if(l==r) return l;
    int k=--CC;
    a.push_back(0);
    b.push_back(0);
    a[-k-1]=create(l,l+r>>1);
    b[-k-1]=create(l+r+2>>1,r);
    return k;
}
vector<int> a_order(int n,int sz,bool ok=1){
    if(n==-1&&ok) return vector<int>(sz,-1);
    if(n>0) return {n};
    vector<int>A=a_order(a[-n-1],sz/2),B=a_order(b[-n-1],sz/2),C;
    for(int i=0;i<A.size();i++)
        C.push_back(A[i]),C.push_back(B[i]);
    return C;
}
void create_circuit(int M, vector<int> A) {
    A.push_back(0);
    int N = A.size(),c=0;
    int k=1<<31-__builtin_clz(2*N-1);
    unneeded=k-N;
    vector<int>C(M+1,-1),s=a_order(create(1,k),k,0);
    for(auto i:s)
        if(i>0)
            mp[i]=A[c++];
    for(auto &i:a)
        if(i>0)i=mp[i];
    for(auto &i:b)
        if(i>0)i=mp[i];
    answer(C,a,b);
}

Compilation message (stderr)

doll.cpp: In function 'int create(int, int)':
doll.cpp:12:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |     a[-k-1]=create(l,l+r>>1);
      |                      ~^~
doll.cpp:13:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     b[-k-1]=create(l+r+2>>1,r);
      |                    ~~~^~
doll.cpp: In function 'std::vector<int> a_order(int, int, bool)':
doll.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:27:16: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |     int k=1<<31-__builtin_clz(2*N-1);
      |              ~~^~~~~~~~~~~~~~~~~~~~~

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