Submission #429095

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
429095	2021-06-15 17:24:11	charterla	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	304 ms	27748 KiB

gift

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 "gift.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Range{
  int ls,rs,self;
}one[500005],two[500005];
int cn[2]={0,0};
bool cmp(Range a,Range b){
  return a.ls==b.ls?a.rs<b.rs:a.ls<b.ls;
}
bool tag[2000005];
bool check(int ls,int rs,int ld,int rd,int now){
  //cout<<ls<<","<<rs<<":"<<ld<<","<<rd<<"-->"<<now<<endl; 
  if(ls<=ld && rd<=rs)return tag[now];
  
  int mid=(ld+rd)/2;
  if(mid>=ls && !check(ls,rs,ld,mid,now<<1))return false;
  if(mid+1<=rs && !check(ls,rs,mid+1,rd,now<<1|1))return false;
  
  return true;
}
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    for(int i=0;i<r;i++){
      if(x[i]==1){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25
• Subtask 5: 30 / 30