Submission #1021183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021183		TheWilp	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	160 ms	29812 KiB

gift

#include "gift.h"
#include <algorithm>

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    std::string s;
    std::vector<std::pair<int,int>> r1,r2;
    for(int q = 0;q < r;q++) {
        if(x[q] == 1) {
            r1.push_back({a[q],b[q]});
        }
        else {
            r2.push_back({a[q],b[q]});
        }
    }
    if(r1.size()) std::sort(r1.begin(),r1.end());
    std::vector<int> v(n);
    std::vector<int> t;
    int place = 0;
    int i = 0;
    for(int q = 0;q < n;q++) {
        while (i < r1.size() && r1[i].first == q) {
            t.push_back(r1[i].second);
            ++i;
        }
        while(t.size() && t.back() <= q) t.pop_back(); 
        v[q] = place;
        if(t.size() == 0)
            place++;
    }
    bool is_yes = true;
    for(int q = 0;q < r2.size();q++){
        if(v[r2[q].first] == v[r2[q].second])  {
            is_yes = false;
            break;
        }
    }
    if(!is_yes) {
        return 0;
    }
    else {
        for(int q = 0;q < n;q++) {
            if(v[q] % 2) {
                s.push_back('R');
            }
            else {
                s.push_back('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:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         while (i < r1.size() && r1[i].first == q) {
      |                ~~^~~~~~~~~~~
gift.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int q = 0;q < r2.size();q++){
      |                   ~~^~~~~~~~~~~

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