| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 465649 | Bidrift | Handcrafted Gift (IOI20_gift) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <string>
#include <fstream>
#include <list>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <iomanip>
#include "gift.h"
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define srt(a) sort(all(a));
#define srtc(a,comp) sort(all(a),comp);
#define srtb(a) sort(a.rbegin(),a.rend());
#define boost ios::sync_with_stdio(false); cin.tie(0); cin.tie(0);
using ll = long long;
using namespace std;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> ii;
typedef vector<ii> vpi;
const int dx[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //right left down up
void setIO(string name = "") { // name is nonempty for USACO file I/O
ios_base::sync_with_stdio(0); cin.tie(0); // see Fast Input & Output
// alternatively, cin.tie(0)->sync_with_stdio(0);
freopen((name+".in").c_str(), "r", stdin); // see Input & Output
freopen((name+".out").c_str(), "w", stdout);
}
int construct(int n, int r, int a[], int b[], int x[]){
string s;
for (int i = 0; i < n; i++){
s.pb('R');
}
vi onesA, onesB;
vpi ones;
for (int i = 0; i < r; i++) if (x[i] == 1) ones.eb(a[i],b[i]);
if (!ones.empty()) {
srt(ones);
int start = ones[0].first;
onesA.pb(start);
int finish = ones[0].second;
for (int i = 1; i < ones.size(); i++) {
if (ones[i].first <= finish) {
finish = max(finish, ones[i].second);
} else {
onesB.pb(finish);
onesA.pb(ones[i].first);
finish = ones[i].second;
}
}
onesB.pb(finish);
}
// twos
vi twosA, twosB;
vpi twos;
for (int i = 0; i < r; i++) if(x[i] == 2) twos.eb(a[i],b[i]);
if (!twos.empty()) {
srt(twos);
int start = twos[0].first;
twosA.pb(start);
int finish = twos[0].second;
for (int i = 1; i < twos.size(); i++) {
if (twos[i].first <= finish) {
finish = max(finish, twos[i].second);
} else {
twosB.pb(finish);
twosA.pb(twos[i].first);
finish = twos[i].second;
}
}
twosB.pb(finish);
}
//for (int i = 0; i < onesA.size(); i++) cout << onesA[i] << " " << onesB[i] << endl;
//for (int i = 0; i < twosA.size(); i++) cout << twosA[i] << " " << twosB[i] << endl;
int one = 0, two = 0;
while (one < onesA.size() && two < twosA.size()){
while (twosA[two] >= onesB[one]){
one++;
}
if (one >= onesA.size()) break;
if (twosB[two] <= onesB[one]){
return 0;
}
}
one = 0, two = 0;
int color = 0; // 0 = red, 1 = blue
for (int i = 0; i < n; i++){
if (one < onesA.size() && two < twosA.size()){
while (onesB[one] < i){
one++;
}
while (twosB[two] < i){
two++;
}
if (onesA[one] > i && twosA[two] > i){
if (color) s[i] = 'B';
else s[i] = 'R';
continue;
}
if (onesA[one] >= i && twosA[two] <= i && twosB[two] >= i){
color^=1;
if (color) s[i] = 'B';
else s[i] = 'R';
continue;
}
if (onesA[one] < i && onesB[one] >= i){
s[i] = s[i-1];
continue;
}
continue;
}
if (one < onesA.size() || (one >= onesA.size() && two >= twosA.size())){
s[i] = s[i-1];
continue;
} else {
color^= 1;
if (color) s[i] = 'B';
else s[i] = 'R';
}
}
craft(s);
return 1;
}