제출 #1318105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318105		nagorn_ph	Handcrafted Gift (IOI20_gift)	C++20	70 / 100	1595 ms	15172 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e9;
const matrix II = {{1, 0}, {0, 1}};
const int N = 5e5 + 5;

int par[N];

int dsu(int a){
    return par[a] = (a == par[a] ? a : dsu(par[a]));
}

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    iota(par, par + N, 0ll);
    int cnt[3] = {0};
    for (int i = 0; i < r; i++) {
        cnt[x[i]]++;
    }
    if (cnt[1] == r) {
        string ss(n, 'R');
        craft(ss);
        return 1;
    }
    if (cnt[2] == r) {
        string ss = "";
        for (int i = 0; i < r; i++) if (a[i] == b[i]) return 0;
        for (int i = 0; i < n; i++) {
            if (i % 2) ss += "R";
            else ss += "B";
        }
        craft(ss);
        return 1;
    }
    string s(n, ' ');
    for (int i = 0; i < r; i++) {
        if (x[i] == 1) {
            for (int j = a[i]; j <= b[i]; j++) {
                if (j < b[i]) par[dsu(j)] = dsu(j + 1);
                s[j] = 'R';
            }
        }
    }
    for (int i = 0; i < r; i++) {
        if (x[i] == 2) {
            if (dsu(a[i]) == dsu(b[i])) return 0;
        }
    }
    for (int i = 0; i < n; i++) {
        if (s[i] != ' ') continue;
        int j = i, idx = 0;
        while (j < n && s[j] == ' ') {
            if (idx % 2 == 0) s[j] = 'B';
            else s[j] = 'R';
            idx++;
            j++;
        }
        i = j - 1;
    }
    craft(s);
    return 1;
}

/*
sub 1: x[i] = 1
just output all "R"

sub 2: x[i] = 2
if (a[i] == b[i]) : return 0;
else return alternating sequence

sub 3: 1 <= n,r <= 18

sub 4: 1 <= n,r <= 2000

sub 5: full sol

*/

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