Submission #952945

#	Time	Username	Problem	Language	Result	Execution time	Memory
952945		kilikuma	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	133 ms	26784 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>

using namespace std;

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    int painting[n + 1] = {0};
    for (int i = 0; i < r; i ++) {
      if (x[i] == 1) {
        painting[b[i] + 1] --;
        painting[a[i]] ++;
      }
    }
    for (int i = 1; i < n; i ++) {
      painting[i] += painting[i - 1];
    }

    int encrypt[n + 1] = {0};
    int ind = 0, color = 0;
    string s(n, 'R');

    while (ind < n) {
      if (painting[ind] == 0) {
        encrypt[ind] = color;
        ind ++;
      }
      else {
        while ((ind < n) and (painting[ind] >= 1)) {
          encrypt[ind] = color;
          ind ++;
        }
      }
      color = (color + 1) % 2;
    }

    for (int i = 0; i < n; i ++) {
      if (encrypt[i] == 0) s[i] = 'R';
      else s[i] = 'B';
    }

    int pref[n + 1] = {0};
    for (int i = 1; i <= n; i ++) {
      pref[i] = encrypt[i] + pref[i - 1];
    }
    for (int i = 0; i < r; i ++) {
      int cible = pref[b[i]] - pref[a[i] - 1];
      int longueur = b[i] - a[i] + 1;
      if (x[i] == 2) {
        if ((0 < cible) and (cible < longueur)) ;
        else {
          return 0;
        }
      }
      else {
        if ((0 < cible) and (cible < longueur)) return 0;
        else ;
      }
    }
    craft(s);
    return 1;
}

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