Submission #465739

#	Time	Username	Problem	Language	Result	Execution time	Memory
465739		MohamedFaresNebili	Handcrafted Gift (IOI20_gift)	C++14	20 / 100	1576 ms	2097156 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>

using namespace std;
int N, R; vector<int>aa, bb, xx; bool used=false;
void solve(int i, string s)
{
    if(used) return;
    if(i==N) {
        bool found=true;
        for(int l=0;l<R&&found;l++) {
            int lo=aa[l], hi=bb[l], v=xx[l];
            if(v==1) {
                int r=0, b=0;
                for(int i=lo;i<=hi;i++) {
                    if(s[i]=='R') r++;
                    if(s[i]=='B') b++;
                }
                if(r!=0&&b!=0) found=false;
            }
			else if(v==2) {
				int r=0, b=0;
				for(int i=lo;i<=hi;i++) {
					if(s[i]=='R') r++;
					if(s[i]=='B') b++;
				}
				if(r==0||b==0) found=false;
			}
        }
        if(found) { used=true; craft(s); }
        return;
    }
    solve(i+1, s+"R"); solve(i+1, s+"B");
}

int construct(int n, int r, std::vector<int> a, std::vector<int> b, std::vector<int> x) {
    N=n; R=r; aa=a; bb=b; xx=x; solve(0, "");
    if(used) return 1;
    return 0;
}

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