Submission #559149

#	Time	Username	Problem	Language	Result	Execution time	Memory
559149		AlperenT	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	297 ms	58104 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){
    string ans(n, 'R');

    vector<pair<int, int>> seg1, seg2;

    for(int i = 0; i < n; i++) seg1.push_back({i, i});

    for(int i = 0; i < r; i++){
        if(x[i] == 1) seg1.push_back({a[i], b[i]});
        else if(x[i] == 2) seg2.push_back({a[i], b[i]});
    }

    vector<int> arr(n, 0);

    int l = 0, mxr = 0, cnt = 0;

    sort(seg1.begin(), seg1.end());

    for(int i = 0; i < seg1.size(); i++){
        if(seg1[i].first <= mxr) mxr = max(mxr, seg1[i].second);
        else{
            cnt++;
            for(int j = l; j <= mxr; j++) arr[j] = cnt;

            l = seg1[i].first, mxr = seg1[i].second;
        }
    }

    cnt++;
    for(int j = l; j <= mxr; j++) arr[j] = cnt;

    char c = 'R';

    ans[0] = c;

    for(int i = 1; i < n; i++){
        if(arr[i] != arr[i - 1]) c = (c == 'R' ? 'B' : 'R'); 

        ans[i] = c;
    }

    vector prefix = vector(n, vector<int>(2, 0));

    prefix[0][0]++;

    for(int i = 1; i < n; i++){
        prefix[i] = prefix[i - 1];

        if(ans[i] == 'R') prefix[i][0]++;
        else if(ans[i] == 'B') prefix[i][1]++;
    }

    for(auto p : seg2){
        vector<int> cur(2, 0);

        cur[0] = prefix[p.second][0] - (p.first == 0 ? 0 : prefix[p.first - 1][0]);
        cur[1] = prefix[p.second][1] - (p.first == 0 ? 0 : prefix[p.first - 1][1]);

        if(cur[0] == 0 || cur[1] == 0) 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:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 0; i < seg1.size(); i++){
      |                    ~~^~~~~~~~~~~~~

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