Submission #671402

#	Time	Username	Problem	Language	Result	Execution time	Memory
671402		amunduzbaev	Port Facility (JOI17_port_facility)	C++17	10 / 100	475 ms	464 KiB

port_facility

#include "bits/stdc++.h"
using namespace std;

const int N = 100;
int a[N], b[N], id[N], w[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	if(n > 20) assert(false);
	for(int i=0;i<n;i++){
		cin >> a[i] >> b[i];
		a[i]--, b[i]--;
		id[a[i]] = id[b[i]] = i;
		w[b[i]] = 1;
	}
	
	int res = 0;
	for(int mask=0;mask < (1 << n);mask++){
		vector<int> p[2];
		bool ok = 1;
		for(int i=0;i<n*2;i++){
			int j = id[i];
			if(w[i]){
				if(p[mask >> j & 1].empty() || p[mask >> j & 1].back() != j){
					ok = 0;
					break;
				} p[mask >> j & 1].pop_back();
			} else {
				p[mask >> j & 1].push_back(j);
			}
		}
		
		if(ok) res++;
	}
	
	cout<<res<<"\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22