Submission #385501

#	Time	Username	Problem	Language	Result	Execution time	Memory
385501		taulant	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	254 ms	26716 KiB

gift

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

void craft(string& s);

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x){
 vector<pii> one, two;
 for(int i = 0; i < r; ++i){
  if(x[i] == 1) one.push_back({a[i], b[i]});
  if(x[i] == 2) two.push_back({a[i], b[i]});
 }
 sort(one.begin(), one.end());
 sort(two.begin(), two.end());
 string ans(n, 'R');
 int f = 1;
 for(auto [l, r] : one){
  while(f <= l){
   ans[f] = ans[f-1] == 'R'? 'B' : 'R';
   ++f;
  }
  while(f <= r){
   ans[f] = ans[f-1];
   ++f;
  }
 }
 while(f < n){
  ans[f] = ans[f-1] == 'R'? 'B' : 'R';
  ++f;
 }
 // constructed a coloring, lets check if it is valid
 vector<int> diff(n, 0);
 for(int i = 1; i < n; ++i) diff[i] = diff[i-1] + (ans[i] != ans[i-1]);
 for(auto [l, r] : two){
  if(diff[l] == diff[r]) return 0;
 }
 craft(ans);
 return 1;
}

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