| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1338819 | edl0231 | Handcrafted Gift (IOI20_gift) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "gift.h"
#include "grader.cpp"
using namespace std;
int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
vector<pair<int, int>> v;
for (int i = 0; i < r; i++)
{
if (x[i] == 1) {v.emplace_back(a[i], b[i]);}
}
sort(v.begin(), v.end());
vector<pair<int, int>> intervals;
int st = -1, curr = -1;
// for (auto i : v) cout << i.first << ' ' << i.second;
for (auto i : v)
{
if (st == -1) {st = i.first, curr = i.second; continue;}
if (i.first > curr) {intervals.emplace_back(st, curr); st = i.first, curr = i.second; continue;}
curr = i.second;
}
if (st != -1) intervals.emplace_back(st, curr);
// for (auto i : intervals) cout << i.first << ' ' << i.second << '\n';
vector<int> w(n);
int ind = 0, ct = 0;
for (auto i : intervals)
{
while (ind < i.first) w[ind] = ct, ind++, ct++;
for (int j = i.first; j <= i.second; j++) w[j] = ct;
ind = i.second + 1, ct++;
}
for (; ind < n; ind++) w[ind++] = ct++;
// for (auto i : w) cout << i << ' ';
for (int i = 0; i < r; i++)
{
if (x[i] == 1) continue;
if (w[a[i]] == w[b[i]]) return 0;
}
string s = "";
for (int i = 0; i < n; i++)
{
if (w[i] & 1) s += 'R';
else s += 'B';
}
craft(s);
return 1;
}
