Submission #366589

#	Time	Username	Problem	Language	Result	Execution time	Memory
366589		PurpleCrayon	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	611 ms	50004 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(v.size())

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    string ans(n, '?');

    vector<vector<ar<int, 2>>> ev(n);

    vector<bool> bad(r, 1);
    for (int i = 0; i < r; i++){
        if (a[i] == b[i]){
            if (x[i] == 2) return 0;
            bad[i] = 0;
            continue;
        }
        ev[a[i]].push_back({0, i});
        ev[b[i]].push_back({1, i});
    }
    for (auto& v : ev) sort(v.begin(), v.end());

    set<int> c[2];
    int cnt[2]={};

    for (int i = 0; i < n; i++){
        if (cnt[0]){
            ans[i] = i?ans[i-1]:'R';

            for (auto v : c[0]) bad[v]=0;
            c[0].clear();
        } else {
            ans[i] = i?ans[i-1]^'R'^'B':'R';
            for (auto v : c[1]) bad[v]=0;
            c[1].clear();
        }

        for (auto e : ev[i]){
            if (e[0] == 0){
                c[x[e[1]]-1].insert(e[1]);
                cnt[x[e[1]]-1]++;
            } else {
                c[x[e[1]]-1].erase(e[1]);
                cnt[x[e[1]]-1]--;
            }
        }
    }

    for (auto v : bad) if (v) return 0;
    
    craft(ans);
    return 1;
}

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