제출 #1318897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318897		ezzzay	Handcrafted Gift (IOI20_gift)	C++20	100 / 100	418 ms	40504 KiB

gift

#include "gift.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x){
    vector<int> ps(n+5,0);
    for(int i=0;i<r;i++){
        if(x[i]==1){
            ps[a[i]]++;
            ps[b[i]]--;
        }
    }
    for(int i=1;i<=n-1;i++) ps[i]+=ps[i-1];
    set<int> st;
    for(int i=0;i<=n-2;i++){
        if(ps[i]==0) st.insert(i);
    }
    for(int i=0;i<r;i++){
        if(x[i]==2 && a[i]==b[i]) return 0;
    }
    vector<int> ed(max(0,n-1),0);
    for(int i=0;i<r;i++){
        if(x[i]==2){
            int L=a[i], R=b[i]-1;
            auto it = st.lower_bound(L);
            if(it==st.end() || *it>R) return 0;
            ed[*it]=1;
        }
    }
    string s;
    char c='B';
    if(n>0) s+=c;
    for(int i=0;i<=n-2;i++){
        if(ed[i]) c = (c=='B' ? 'R' : 'B');
        s+=c;
    }
    for(int i=0;i<n+5;i++) ps[i]=0;
    for(int i=0;i<n;i++) ps[i+1]=ps[i]+(s[i]=='R');
    for(int i=0;i<r;i++){
        int r = ps[b[i]+1]-ps[a[i]];
        int len = b[i]-a[i]+1;
        if(x[i]==1){
            if(!(r==len || r==0)) return 0;
        } else {
            if(r==len || r==0) return 0;
        }
    }
    craft(s);
    return 1;
}

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