Submission #1317031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317031		hyyh	Handcrafted Gift (IOI20_gift)	C++20	100 / 100	78 ms	17016 KiB

gift

#include "gift.h"

using namespace std;

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    std::string s(n, 'R');
    vector<int> vc1(n,-1);
    vector<int> vc2(n,1e9);
    for(int i = 0;i < r;i++){
        if(x[i] == 1) vc1[a[i]] = max(vc1[a[i]],b[i]);
        else vc2[a[i]] = min(vc2[a[i]],b[i]);
    }
    int cur = 0;
    for(int i = 0;i < n;i++){
        if(i > cur){
            if(s[i-1] == 'R') s[i] = 'B';
            else s[i] = 'R';
        }
        else if(i > 0){
            s[i] = s[i-1];
        }
        if(vc1[i] != -1){
            cur = max(cur,vc1[i]);
        }
    }
    cur = 1e9;
    for(int i = 0;i < n;i++){
        if(i > 0 && s[i-1] != s[i]) cur = 1e9;
        if(vc2[i] != 1e9){
            cur = min(cur,vc2[i]);
        }
        if(i >= cur) 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