Submission #1242058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242058		hiikunZ	Handcrafted Gift (IOI20_gift)	C++20	100 / 100	86 ms	18948 KiB

gift

#include "gift.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int construct(int n,int r,std::vector<int> a,std::vector<int> b,std::vector<int> x) {
    vector<int> memo(n,-1),aka(n+1,0),ao(n+1,0);
    string S;
    for(ll i = 0;i < r;i++){
        if(x[i] == 1 && a[i] != b[i]){
            memo[a[i]] = max(memo[a[i]],b[i]);
        }
    }
    int sibari = -1;
    for(ll i = 0;i < n;i++){
       
        if(i == 0) S += 'R';
        else if(i <= sibari) S += S.back();
        else S += ('R' + 'B' - S.back());
        aka[i + 1] = aka[i] + (S.back() == 'R');
        ao[i + 1] = ao[i] + (S.back() == 'B');
        sibari = max(sibari,memo[i]);
    }
    for(ll i = 0;i < r;i++){
        if(x[i] == 1){
            if(aka[b[i] + 1] - aka[a[i]] != 0 && ao[b[i] + 1] - ao[a[i]] != 0) return 0;
        }
        else{
            if(aka[b[i] + 1] - aka[a[i]] == 0 || ao[b[i] + 1] - ao[a[i]] == 0) return 0;
        }
    }
    
    craft(S);
    return 1;
}

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