Submission #385471

#	Time	Username	Problem	Language	Result	Execution time	Memory
385471		taulant	Handcrafted Gift (IOI20_gift)	C++17	10 / 100	245 ms	26708 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 < 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;
}

Compilation message (stderr)

gift.cpp: In function 'int construct(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
gift.cpp:37:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   while(idx < two.size() && two[idx].first < diff){
      |         ~~~~^~~~~~~~~~~~

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