Submission #415529

#	Time	Username	Problem	Language	Result	Execution time	Memory
415529		Pro_ktmr	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	318 ms	43760 KiB

gift

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
#define repi(i, a, b) for(int (i)=(a); (i)<(b); (i)++)

#include "gift.h"

vector<int> q1[500000];

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    rep(i, r){
        if(x[i] == 1) q1[a[i]].pb(b[i]);
    }

    vector<int> S(n, -1);
    S[0] = 0;
    int d = 0;
    rep(i, n){
        if(d < i){
            S[i] = S[i-1] ^ 1;
            d = i;
        }
        rep(j, q1[i].size()){
            repi(k, d+1, q1[i][j]+1){
                S[k] = S[i];
                d = k;
            }
        }
    }

    vector<int> sum(n+1, 0);
    rep(i, n) sum[i+1] = sum[i] + S[i];

    rep(i, r){
        if(x[i] == 2){
            int c = sum[b[i]+1] - sum[a[i]];
            if(c == 0 || c == b[i]+1-a[i]) return 0;
        }
    }

    string s(n, '?');
    rep(i, n){
        s[i] = (S[i] == 0 ? 'R' : 'B');
    }
    craft(s);
    return 1;
}

Compilation message (stderr)

gift.cpp: In function 'int construct(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
gift.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
gift.cpp:13:5: note: in expansion of macro 'rep'
   13 |     rep(i, r){
      |     ^~~
gift.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
gift.cpp:20:5: note: in expansion of macro 'rep'
   20 |     rep(i, n){
      |     ^~~
gift.cpp:5:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
gift.cpp:25:9: note: in expansion of macro 'rep'
   25 |         rep(j, q1[i].size()){
      |         ^~~
gift.cpp:5:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                                  ~~~^~~~
gift.cpp:25:9: note: in expansion of macro 'rep'
   25 |         rep(j, q1[i].size()){
      |         ^~~
gift.cpp:6:31: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    6 | #define repi(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
      |                               ^
gift.cpp:26:13: note: in expansion of macro 'repi'
   26 |             repi(k, d+1, q1[i][j]+1){
      |             ^~~~
gift.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
gift.cpp:34:5: note: in expansion of macro 'rep'
   34 |     rep(i, n) sum[i+1] = sum[i] + S[i];
      |     ^~~
gift.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
gift.cpp:36:5: note: in expansion of macro 'rep'
   36 |     rep(i, r){
      |     ^~~
gift.cpp:5:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
gift.cpp:44:5: note: in expansion of macro 'rep'
   44 |     rep(i, n){
      |     ^~~

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