답안 #888608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888608	2023-12-18T01:35:18 Z	thunopro	Passport (JOI23_passport)	C++14	22 / 100	2000 ms	37720 KB

passport

#include<bits/stdc++.h>
using namespace std ;
#define maxn 200009 
#define ll long long
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 
const int LOG = 18 ; 

typedef vector<int> vi ; 
typedef vector<ll> vl ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 
typedef pair<ll,ll> pll ;  

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a < 0 ) a += mod ; 
	if ( a >= mod ) a -= mod ; 
}

template < typename T > void chkmin (T &a , T b) { if (a>b) a=b ;} 
template < typename T > void chkmax (T &a , T b) { if (a<b) a=b ;}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
//	freopen ("bai1.out","w",stdout) ; 
}

int n ; 
pii a [maxn] ; 

bool is_query [maxn] ;

void sub1 () 
{
	priority_queue <int> S ; 
	for ( int i = 1 ; i <= a [1].se ; i ++ ) S.push(a[i].se) ; 
	int res = 1 ; 
	int cur = a[1].se ; 
	while ( !S.empty () ) 
	{
		int u = S.top() ; S.pop() ; 
		if ( cur >= u ) break ; 
		while ( cur < u ) S . push (a[++cur].se) ; 
		res ++ ; 
	}
	if ( cur >= n ) cout << res ; 
	else cout << -1 ; 
} 

int dp [3009][3009] ; 
void sub2 () 
{
	int pos ; 
	for ( int i = 1 ; i <= n ; i ++ ) if ( is_query [i] ) pos = i ; 
	memset ( dp , 0x3f , sizeof dp ) ; 
	
	dp [pos][pos] = 0 ; 
	for ( int len = 0 ; len <= n-1 ; len ++ )
	{
		for ( int l = 1 ; l <= n ; l ++ ) 
		{
			int r = l + len ; 
			if ( r > n ) break ; 
			if ( dp [l][r] > 1e9 ) continue ; 
			for ( int i = l ; i <= r ; i ++ ) 
			{
				chkmin (dp[min(l,a[i].fi)][max(r,a[i].se)],dp[l][r]+1) ; 
			}
		}
	}

	if ( dp [1][n] > 1e9 ) dp [1][n] = - 1 ; 
	cout << dp [1][n] ; 
}
int main () 
{
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; cout.tie(0) ; 
//	rf () ; 
	
	cin >> n ; 
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i].fi >> a[i].se ; 
	
	int nq ; cin >> nq ; 
	for ( int i = 1 ; i <= nq ; i ++ ) 
	{
		int x ; cin >> x ; 
		is_query [x] = true ; 
	}

	if ( nq == 1 && is_query [1] == true ) sub1 () ; 
	else sub2 () ; 
}

Compilation message

passport.cpp: In function 'void rf()':
passport.cpp:34:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
passport.cpp: In function 'void sub2()':
passport.cpp:67:16: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |  dp [pos][pos] = 0 ;
      |  ~~~~~~~~~~~~~~^~~

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	26 ms	3664 KB	Output is correct
5	Correct	30 ms	3540 KB	Output is correct
6	Correct	24 ms	2648 KB	Output is correct
7	Correct	20 ms	3548 KB	Output is correct
8	Correct	17 ms	3160 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	8 ms	37468 KB	Output is correct
3	Correct	1 ms	2520 KB	Output is correct
4	Correct	1 ms	2520 KB	Output is correct
5	Correct	5 ms	37468 KB	Output is correct
6	Correct	5 ms	37464 KB	Output is correct
7	Correct	5 ms	37468 KB	Output is correct
8	Correct	5 ms	37516 KB	Output is correct
9	Correct	5 ms	37576 KB	Output is correct
10	Correct	5 ms	37328 KB	Output is correct
11	Correct	5 ms	37464 KB	Output is correct
12	Correct	6 ms	37468 KB	Output is correct
13	Correct	5 ms	37720 KB	Output is correct
14	Correct	5 ms	37324 KB	Output is correct
15	Correct	7 ms	37468 KB	Output is correct

Subtask #3
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	8 ms	37468 KB	Output is correct
3	Correct	1 ms	2520 KB	Output is correct
4	Correct	1 ms	2520 KB	Output is correct
5	Correct	5 ms	37468 KB	Output is correct
6	Correct	5 ms	37464 KB	Output is correct
7	Correct	5 ms	37468 KB	Output is correct
8	Correct	5 ms	37516 KB	Output is correct
9	Correct	5 ms	37576 KB	Output is correct
10	Correct	5 ms	37328 KB	Output is correct
11	Correct	5 ms	37464 KB	Output is correct
12	Correct	6 ms	37468 KB	Output is correct
13	Correct	5 ms	37720 KB	Output is correct
14	Correct	5 ms	37324 KB	Output is correct
15	Correct	7 ms	37468 KB	Output is correct
16	Correct	883 ms	37716 KB	Output is correct
17	Correct	744 ms	37580 KB	Output is correct
18	Correct	25 ms	37468 KB	Output is correct
19	Correct	34 ms	37576 KB	Output is correct
20	Execution timed out	2057 ms	37468 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #4
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	8 ms	37468 KB	Output is correct
3	Correct	1 ms	2520 KB	Output is correct
4	Correct	1 ms	2520 KB	Output is correct
5	Correct	5 ms	37468 KB	Output is correct
6	Correct	5 ms	37464 KB	Output is correct
7	Correct	5 ms	37468 KB	Output is correct
8	Correct	5 ms	37516 KB	Output is correct
9	Correct	5 ms	37576 KB	Output is correct
10	Correct	5 ms	37328 KB	Output is correct
11	Correct	5 ms	37464 KB	Output is correct
12	Correct	6 ms	37468 KB	Output is correct
13	Correct	5 ms	37720 KB	Output is correct
14	Correct	5 ms	37324 KB	Output is correct
15	Correct	7 ms	37468 KB	Output is correct
16	Correct	883 ms	37716 KB	Output is correct
17	Correct	744 ms	37580 KB	Output is correct
18	Correct	25 ms	37468 KB	Output is correct
19	Correct	34 ms	37576 KB	Output is correct
20	Execution timed out	2057 ms	37468 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	26 ms	3664 KB	Output is correct
5	Correct	30 ms	3540 KB	Output is correct
6	Correct	24 ms	2648 KB	Output is correct
7	Correct	20 ms	3548 KB	Output is correct
8	Correct	17 ms	3160 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	8 ms	37468 KB	Output is correct
11	Correct	1 ms	2520 KB	Output is correct
12	Correct	1 ms	2520 KB	Output is correct
13	Correct	5 ms	37468 KB	Output is correct
14	Correct	5 ms	37464 KB	Output is correct
15	Correct	5 ms	37468 KB	Output is correct
16	Correct	5 ms	37516 KB	Output is correct
17	Correct	5 ms	37576 KB	Output is correct
18	Correct	5 ms	37328 KB	Output is correct
19	Correct	5 ms	37464 KB	Output is correct
20	Correct	6 ms	37468 KB	Output is correct
21	Correct	5 ms	37720 KB	Output is correct
22	Correct	5 ms	37324 KB	Output is correct
23	Correct	7 ms	37468 KB	Output is correct
24	Correct	883 ms	37716 KB	Output is correct
25	Correct	744 ms	37580 KB	Output is correct
26	Correct	25 ms	37468 KB	Output is correct
27	Correct	34 ms	37576 KB	Output is correct
28	Execution timed out	2057 ms	37468 KB	Time limit exceeded
29	Halted	0 ms	0 KB	-

답안 #888608

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 16.0 / 16.0

Subtask #3 0 / 24.0

Subtask #4 0 / 8.0

Subtask #5 0 / 46.0

Subtask #1
6.0 / 6.0

Subtask #2
16.0 / 16.0

Subtask #3
0 / 24.0

Subtask #4
0 / 8.0

Subtask #5
0 / 46.0