Submission #385496

#	Time	Username	Problem	Language	Result	Execution time	Memory
385496		taulant	Handcrafted Gift (IOI20_gift)	C++17	10 / 100	261 ms	19412 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> vld(two.size(), 1);
 int diff = 1, idx = 0;
 while(diff < n){
  while(diff < n && ans[diff] == ans[diff - 1]) ++diff;
  if(diff == n) break;
  while(idx < int(two.size()) && two[idx].first < diff){
   if(two[idx].second >= diff) vld[idx] = 1;
   ++idx;
  }
  ++diff;
 }
 for(int i : vld) if(!i) return 0;
 craft(ans);
 return 1;
}

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