Submission #559416

#	Time	Username	Problem	Language	Result	Execution time	Memory
559416		PiejanVDC	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	154 ms	20140 KiB

gift

#include <bits/stdc++.h>
#include "gift.h"

using namespace std;

int construct(int n, int r, vector<int>a, vector<int>b, vector<int>x) {
    vector<int>one(n+1, 0), start(n, 0);
    for(int i = 0 ; i < r ; i++) {
        if(x[i] == 1)
            one[a[i]]++, one[b[i]+1]--, start[a[i]]++;
    }
    int cnt = 0;
    char C = 'R';
    auto c = [&] (char X) -> char {
        if(X == 'R')
            return 'B';
        return 'R';
    };
    string s = "";
    vector<int>change(n+1,0);
    for(int i = 0 ; i < n ; i++) {
        cnt += one[i];
        change[i+1] = change[i];
        if(!cnt || start[i] == cnt) {
            change[i+1]++;
            C = c(C);
        }
        s += C;
    }
    bool ok = 1;
    for(int i = 0 ; i < r ; i++) {
        if(x[i] == 1) {
            if(change[b[i]+1] - change[a[i]+1] != 0)
                ok = 0;
        } else {
            if(change[b[i]+1] - change[a[i]+1] == 0)
                ok = 0;
        }
    }
    if(!ok)
        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