Submission #425485

#	Time	Username	Problem	Language	Result	Execution time	Memory
425485		chirathnirodha	Handcrafted Gift (IOI20_gift)	C++17	100 / 100	284 ms	28656 KiB

gift

//Coded by Chirath Nirodha
#include<bits/stdc++.h>
using namespace std;
#include "gift.h"
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long ll;

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
    string s(n, 'R');
    int group[n];
    for(int i=0;i<n;i++)group[i]=i;
    vector<pair<int,pair<int,int> > > v;
    for(int i=0;i<r;i++)v.PB(MP(x[i],MP(a[i],b[i])));
    sort(v.begin(),v.end());
    for(int i=0;i<r;i++){
        int p=v[i].S.F,q=v[i].S.S;
        if(v[i].F==1){
            for(int j=q;j>=p;j--){
                if(group[j]==group[p])break;
                group[j]=group[p];
            }
        }
        else if(group[p]==group[q])return 0;
    }
    for(int i=1;i<n;i++){
        if(group[i]==group[i-1])s[i]=s[i-1];
        else {
            if(s[i-1]=='R')s[i]='B';
            else s[i]='R';
        }
    }
    craft(s);
    return 1;
}

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