Submission #1078481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078481		mindiyak	Handcrafted Gift (IOI20_gift)	C++14	70 / 100	219 ms	27576 KiB

gift

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

using namespace std;

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    vector<int> arr(n,0),presum(n+1,0);

    vector<pair<int,int>> p,q,t;
    for(int i=0;i<r;i++){
        if(x[i] == 1)p.push_back({a[i],b[i]});
        if(x[i] == 2)q.push_back({a[i],b[i]});
    }
    sort(p.begin(),p.end());
    
    if(p.size()>0){
        int start = p[0].first,end = p[0].second;
        for(int i = 1;i<p.size();i++){
            if(p[i].first <= end){
                end = max(end,p[i].second);
            }else{
                t.push_back({start,end});
                start = p[i].first;
                end = p[i].second;
            }
        }
        t.push_back({start,end});

        for(int i=0;i<t.size();i++){
            cerr << (i%2)+1 << " " << t[i].first << " " << t[i].second << endl;
            for(int j=t[i].first;j<=t[i].second;j++){
                // arr[j] = (i%2)+1;
                arr[j] = 2;
            }
        }
    }

    if(arr[0] == 0)arr[0] = 1;
    for(int i=1;i<n;i++){
        if(arr[i] == 0)arr[i] = (arr[i-1]%2) + 1;
    }
    
    for(int i=1;i<=n;i++){
        presum[i] = presum[i-1] + arr[i-1];
    }

    for(int i=0;i<q.size();i++){
        int len = q[i].second - q[i].first + 1;
        int val = presum[q[i].second+1] - presum[q[i].first];
        if(len == val) return 0;
        if(len*2 == val) return 0;
    }

    string s = "";
    for(int i=0;i<n;i++)s += (arr[i] == 1) ? "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:20:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int i = 1;i<p.size();i++){
      |                       ~^~~~~~~~~
gift.cpp:31: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]
   31 |         for(int i=0;i<t.size();i++){
      |                     ~^~~~~~~~~
gift.cpp:49: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]
   49 |     for(int i=0;i<q.size();i++){
      |                 ~^~~~~~~~~

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