Submission #1231224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231224		AndreasK	Handcrafted Gift (IOI20_gift)	C++20	100 / 100	288 ms	44728 KiB

gift

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

#define designed ios_base::sync_with_stdio(0);
#define by cin.tie(0);
#define AndreasK cout.tie(0);
//#define int long long
#define akinput freopen("akinput.txt", "r", stdin);
#define akoutput freopen("akoutput.txt", "w", stdout);

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    set<int> unoccupied;
    for (int c = 0; c < n; c++)
        unoccupied.insert(c);
    vector<pair<pair<int, int>, int> > all;
    for (int c = 0; c < r; c++)
        all.push_back({{a[c], b[c]}, x[c]});
    sort(all.begin(), all.end());
    vector<int> start(n, -1);
    for (auto aek : all) {
        if (aek.second == 2)
            continue;
        if (unoccupied.count(aek.first.first)) {
            start[aek.first.first] = aek.first.first;
            for (int c = aek.first.first; c <= aek.first.second; c++) {
                start[c] = start[aek.first.first];
                unoccupied.erase(c);
            }
        }
        else {
            auto f = unoccupied.lower_bound(aek.first.first);
            set<int> s;
            while (f != unoccupied.end() && *f <= aek.first.second) {
                s.insert(*f);
                f++;
            }
            for (auto aekole : s) {
                start[aekole] = start[aek.first.first];
                unoccupied.erase(aekole);
            }
        }
    }
    for (int c = 0; c < n; c++)
        if (start[c] == -1) {
            start[c] = n + c;
        }
    for (int c = 0; c < r; c++) {
        if (x[c] == 1) {
            continue;
        }
        else
            if (start[a[c]] == start[b[c]])
                return 0;
    }
    string s = "";
    s += 'R';
    for (int c = 1; c < n; c++) {
        if (start[c] == start[c - 1])
            s += s[s.size() - 1];
        else
            if (s[s.size() - 1] == 'R')
                s += 'B';
            else
                s += 'R';
    }
    craft(s);
    return 1;
}

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