oj.uz

Submission #889215

# Submission time Handle Problem Language Result Execution time Memory
889215 2023-12-19T08:03:06 Z Minbaev Port Facility (JOI17_port_facility) C++17
10 / 100
 203 ms 600 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int mod= 1e9 +7;
const int N=1e5*4;

int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}
void solve(){
	int n,m,k;

	cin>>n;
	
	vector<pair<int,pii>>v;
	
	for(int i = 0;i<n;i++){
		int l,r;
		cin>>l>>r;
		v.pb({l,{1,i}});
		v.pb({r,{2,i}});
	}
	sort(all(v));
	int ans = 0;
	vector<int>vis(n);
	for(int mask = 0;mask<(1<<n);mask++){
		
		deque<int>q1,q2;
		bool flag = true;
		int cnt = 0,cont = 0;
		for(int i = 0;i<n*2;i++){
			
			if(v[i].s.f==1){
				if(((mask>>cnt)&1)==1){
					q2.push_back({v[i].s.s});
					vis[v[i].s.s] = 2;
				}
				if(((mask>>cnt)&1)==0){
					q1.push_back({v[i].s.s});
					vis[v[i].s.s] = 1;
				}
				cnt++;
			}
			else{
				if(vis[v[i].s.s]==1){
					if(q1.back()!=v[i].s.s){
						flag = false;
						break;
					}
					q1.pop_back();
				}
				else{
					if(q2.back()!=v[i].s.s){
						flag = false;
						break;
					}
					q2.pop_back();
				}
			}
		}
		if(flag)ans++;
	}
		


	cout<<ans<<"\n";






}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int cnt=0;
	int tt=1;//cin>>tt;
	while(tt--)solve();

}

Compilation message

port_facility.cpp: In function 'void solve()':
port_facility.cpp:53:15: warning: unused variable 'cont' [-Wunused-variable]
   53 |   int cnt = 0,cont = 0;
      |               ^~~~
port_facility.cpp:34:8: warning: unused variable 'm' [-Wunused-variable]
   34 |  int n,m,k;
      |        ^
port_facility.cpp:34:10: warning: unused variable 'k' [-Wunused-variable]
   34 |  int n,m,k;
      |          ^
port_facility.cpp: In function 'int main()':
port_facility.cpp:103:6: warning: unused variable 'cnt' [-Wunused-variable]
  103 |  int cnt=0;
      |      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 344 KB Output is correct
2 Correct 18 ms 348 KB Output is correct
3 Correct 87 ms 348 KB Output is correct
4 Correct 72 ms 432 KB Output is correct
5 Correct 35 ms 344 KB Output is correct
6 Correct 102 ms 344 KB Output is correct
7 Correct 42 ms 348 KB Output is correct
8 Correct 21 ms 344 KB Output is correct
9 Correct 143 ms 592 KB Output is correct
10 Correct 44 ms 348 KB Output is correct
11 Correct 27 ms 348 KB Output is correct
12 Correct 129 ms 344 KB Output is correct
13 Correct 49 ms 348 KB Output is correct
14 Correct 53 ms 348 KB Output is correct
15 Correct 203 ms 436 KB Output is correct
16 Correct 75 ms 344 KB Output is correct
17 Correct 17 ms 344 KB Output is correct
18 Correct 65 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 344 KB Output is correct
2 Correct 18 ms 348 KB Output is correct
3 Correct 87 ms 348 KB Output is correct
4 Correct 72 ms 432 KB Output is correct
5 Correct 35 ms 344 KB Output is correct
6 Correct 102 ms 344 KB Output is correct
7 Correct 42 ms 348 KB Output is correct
8 Correct 21 ms 344 KB Output is correct
9 Correct 143 ms 592 KB Output is correct
10 Correct 44 ms 348 KB Output is correct
11 Correct 27 ms 348 KB Output is correct
12 Correct 129 ms 344 KB Output is correct
13 Correct 49 ms 348 KB Output is correct
14 Correct 53 ms 348 KB Output is correct
15 Correct 203 ms 436 KB Output is correct
16 Correct 75 ms 344 KB Output is correct
17 Correct 17 ms 344 KB Output is correct
18 Correct 65 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 23 ms 600 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 344 KB Output is correct
2 Correct 18 ms 348 KB Output is correct
3 Correct 87 ms 348 KB Output is correct
4 Correct 72 ms 432 KB Output is correct
5 Correct 35 ms 344 KB Output is correct
6 Correct 102 ms 344 KB Output is correct
7 Correct 42 ms 348 KB Output is correct
8 Correct 21 ms 344 KB Output is correct
9 Correct 143 ms 592 KB Output is correct
10 Correct 44 ms 348 KB Output is correct
11 Correct 27 ms 348 KB Output is correct
12 Correct 129 ms 344 KB Output is correct
13 Correct 49 ms 348 KB Output is correct
14 Correct 53 ms 348 KB Output is correct
15 Correct 203 ms 436 KB Output is correct
16 Correct 75 ms 344 KB Output is correct
17 Correct 17 ms 344 KB Output is correct
18 Correct 65 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 23 ms 600 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 344 KB Output is correct
2 Correct 18 ms 348 KB Output is correct
3 Correct 87 ms 348 KB Output is correct
4 Correct 72 ms 432 KB Output is correct
5 Correct 35 ms 344 KB Output is correct
6 Correct 102 ms 344 KB Output is correct
7 Correct 42 ms 348 KB Output is correct
8 Correct 21 ms 344 KB Output is correct
9 Correct 143 ms 592 KB Output is correct
10 Correct 44 ms 348 KB Output is correct
11 Correct 27 ms 348 KB Output is correct
12 Correct 129 ms 344 KB Output is correct
13 Correct 49 ms 348 KB Output is correct
14 Correct 53 ms 348 KB Output is correct
15 Correct 203 ms 436 KB Output is correct
16 Correct 75 ms 344 KB Output is correct
17 Correct 17 ms 344 KB Output is correct
18 Correct 65 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Incorrect 23 ms 600 KB Output isn't correct
26 Halted 0 ms 0 KB -