Submission #306554

#	Time	Username	Problem	Language	Result	Execution time	Memory
306554		peti1234	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	195 ms	15152 KiB

gift

#include <bits/stdc++.h>
#include "gift.h"
using namespace std;
const int c=500002;
int el[c];
string s;
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    for (int i=0; i<n; i++) el[i]=i;
    for (int i=0; i<r; i++) if (x[i]==1) el[b[i]]=min(el[b[i]], a[i]);
    for (int i=n-2; i>=0; i--) el[i]=min(el[i], el[i+1]);
    for (int i=0; i<n; i++) el[i]=el[el[i]];
    for (int i=0; i<n; i++) s+='R';
    for (int i=0; i<r; i++) if (x[i]==2) if (el[b[i]]<=a[i]) return 0;
    for (int i=1; i<n; i++) {
        if (el[i]!=i) s[i]=s[i-1];
        else if (s[i-1]=='R') s[i]='B';
    }
    craft(s);
    return 1;
}

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