Submission #330677

#	Time	Username	Problem	Language	Result	Execution time	Memory
330677		northlake	Handcrafted Gift (IOI20_gift)	C++17	60 / 100	1576 ms	27096 KiB

gift

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

using namespace std;

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    int union_find[n];
    for (int i = 0; i < n; i++) {
        union_find[i] = i;
    }

    vector<pair<int, int>> one_requirements {};
    vector<pair<int, int>> two_requirements {};
    for (int i= 0; i < r; i++) {
        if (x[i] == 1) {
            one_requirements.push_back({a[i], b[i]});
        }
        else {
            two_requirements.push_back({a[i], b[i]});
        }
    }
    sort(one_requirements.begin(), one_requirements.end());

    for (auto t : one_requirements) {
        int f = t.first;
        int g = t.second;
        for (int j = f+1; j <= g; j++) {
            union_find[j] = union_find[f];
        }
    }

    for (auto t : two_requirements) {
        int f = t.first;
        int g = t.second;
        if (union_find[f] == union_find[g]) return 0;
    }

    string s = "R";
    bool red = true;
    for (int i = 1; i < n; i++) {
        if (union_find[i] != union_find[i-1]) red = !red;
        if (red) s += 'R';
        else s += 'B';
    }

    craft(s);
    return 1;
}

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