Submission #559585

#	Time	Username	Problem	Language	Result	Execution time	Memory
559585		neki	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	297 ms	66112 KiB

gift

#include <bits/stdc++.h>
#include "gift.h"
#define ll long long
#define vc vector
using namespace std;


int construct(int n, int r, vc<int> a, vc<int> b, vc<int> x){
    
    vc<vc<vc<int>>> ques(3, vc<vc<int>> (n));
    for(int i=0;i<r;++i) ques[x[i]][b[i]].push_back(a[i]);
    
    vc<pair<int, int>> ints;
    for(int i=0;i<n;++i){
        for(auto q: ques[1][i]){
            while(ints.size() and q<=ints.back().second) ints.pop_back();
        }
        if(ints.size()==0) ints.emplace_back(0, i);
        else if(ints.back().second<i) ints.emplace_back(ints.back().second+1, i);
    }
    
    int br=1, j=0;
    for(int i=0;i<n;++i){
        while(ints[j].second<i)++j;
        for(auto q: ques[2][i]) if(ints[j].first<=q) br=0;
    }
    
    if(br){
        string ans="";
        char cur='R';
        for(auto i:ints){
            for(int j=i.first;j<=i.second;++j) ans+=cur;
            
            if(cur=='R') cur='B';
            else cur='R';
        }
        craft(ans);
        return 1;
    }
    else return 0;
}

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