제출 #198067

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
198067	2020-01-24 15:14:47	DavidDamian	자동 인형 (IOI18_doll)	C++11	53 / 100	148 ms	20116 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"
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x<<endl
vector<int> destino[100006];
int X[4000006];
int Y[4000006];
int create_tree(int i,int limit,int lv,int sum,int n,int root,int trigger)
{
    int last=i;
    if(lv==limit-1){
        int threshold=(1<<limit)-n;
        if(sum<threshold)
            X[(i+root-1)-1]=-root;
        else
            X[(i+root-1)-1]=destino[trigger][sum-threshold];
        sum+=(1<<lv);
        //debug(sum);
        if(sum<threshold)
            Y[(i+root-1)-1]=-root;
        else
            Y[(i+root-1)-1]=destino[trigger][sum-threshold];
    }
    else{
        X[i+root-1-1]=-(2*i+root-1);
        last=max(last,create_tree(i*2,limit,lv+1,sum,n,root,trigger));
        Y[i+root-1-1]=-(2*i+root);
        last=max(last,create_tree(i*2+1,limit,lv+1,sum+(1<<lv),n,root,trigger));
    }
    return last;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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