Submission #297175

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
297175	2020-09-11 10:23:50	amiratou	Mechanical Doll (IOI18_doll)	C++14	53 / 100	204 ms	20444 KiB

doll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = (int)(1e5+5);
#define sz(x) (int)(x.size())
int log_2(int x){
    return 31-__builtin_clz(x);
}
vector<int> occ[MX],C;
bool state[4*MX],last[4*MX];
int idx=1,X[4*MX],Y[4*MX],a[2*MX];
// fix indexes 2*i is wrong, must assign indexes dynamically 
void gimme(int x){
    //sz(oc[x])==1
    int nb=(1<<(log_2(sz(occ[x])-1)+1))-1;
    int sum=0,st=idx+1,comp=0;
    vector<int> vec={idx};
    while((sum+sz(vec))< nb){
        vector<int> G;
        for(auto it:vec){
            X[it]=-st;
            G.push_back(st),st++;
            Y[it]=-st;
            G.push_back(st),st++;
        }
        sum+=sz(vec);
        vec=G;
    }
    C[x]=-idx;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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