Submission #953470

#	Time	Username	Problem	Language	Result	Execution time	Memory
953470		willychan	Port Facility (JOI17_port_facility)	C++17	10 / 100	169 ms	600 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
/*

is I know the division, checking will be if there a segment that intersegt and not entirly contain.

i think this is a dp problem.. 

every segment will have some segment that it cannot be together with.. , count the number of partition


*/
const int MOD = 1e9+7;

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;	
	if(n>20) return 0;
	vector<pair<int,int> > seg(n+1);
	for(int i=1;i<=n;i++) cin>>seg[i].first>>seg[i].second;
	vector<int> action(2*n+1);
	for(int i=1;i<=n;i++){
		action[seg[i].first]=i;
		action[seg[i].second]=-i;
	}
	sort(seg.begin(),seg.end());
	int ans=0;
	for(int m=0;m<(1<<n);m++){
		bool ok=1;
		stack<int> f[2];
		for(int i=1;i<=2*n;i++){
			bool k = (m>>(abs(action[i])-1))&1;
			if(action[i]>0){
				f[k].push(action[i]);
			}else{
				if(f[k].top()!=-action[i]){
				 	ok=0;
					break;
				}
				f[k].pop();
			}
		}
		if(ok) ans++;
	}
	assert(((ans-(ans&-ans)))==0);

	cout<<ans<<"\n";

	return 0;
}

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