oj.uz

Submission #888971

# Submission time Handle Problem Language Result Execution time Memory
888971 2023-12-18T14:00:10 Z thunopro Festivals in JOI Kingdom 2 (JOI23_festival2) C++14
10 / 100
 4659 ms 2508 KB 
#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); 

 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 , p ; 


int a [maxn] , b [maxn] ; 
int res ; 
pii c [maxn] ; 
bool cmp ( pii u , pii v ) 
{
	return u.se < v.se ; 
}
int x [maxn] ; 
bool used [maxn] ; 

void backtrack ( int pos ) 
{
	if ( pos == n+1 ) 
	{
		int num = 0 ; 
		for ( int i = 1 ; i <= 2*n ; i ++ ) 
		{
			if ( used [i] == 0 ) b [++num] = i ; 
		}	
		do{
			bool ok = true ; 
			for ( int i = 1 ; i <= n ; i ++ ) 
			{
				if ( a [i] > b [i] ) ok = false ; 
			} 
			if ( ok == false ) continue ; 
			for ( int i = 1 ; i <= n ; i ++ ) c [i] = {a[i],b[i]} ; 
			sort (c+1,c+n+1,cmp) ; 
			int last = 0 ; 
			int Max = 0 ; 
			for ( int i = 1 ; i <= n ; i ++ ) 
			{
				if ( c[i].fi > last ) Max ++ , last = c[i].se ; 
				else last = min (last,c[i].se) ; 
			}
			int ans = 0 ; 
			last = 0 ; 
			for ( int i = 1 ; i <= n ; i ++ ) 
			{
				if ( a [i] > last ) ans ++ , last = b [i] ; 
			}
	
			if ( Max != ans ) res ++ ; 
		} while (next_permutation (b+1,b+n+1)) ; 
		return ; 
	}
	for ( int i = a [pos-1] + 1 ; i <= 2*n ; i ++ ) 
	{
		a [pos] = i ; 
		used [i] = true ; 
		backtrack (pos+1) ;
		used [i] = false ;  
	}
}
void sub1 () 
{
	backtrack (1) ; 
	cout << res ; 
}
int main () 
{
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; cout.tie(0) ; 
//	rf () ; 
	cin >> n >> p ;
	mod = p ; 
	
	if ( n <= 8 ) sub1 () ; 
}

Compilation message

festival2.cpp: In function 'void rf()':
festival2.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) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2408 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2408 KB Output is correct
8 Correct 4515 ms 2504 KB Output is correct
9 Correct 4622 ms 2504 KB Output is correct
10 Correct 4659 ms 2504 KB Output is correct
11 Correct 7 ms 2392 KB Output is correct
12 Correct 164 ms 2508 KB Output is correct
13 Correct 166 ms 2504 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2408 KB Output is correct
8 Correct 4515 ms 2504 KB Output is correct
9 Correct 4622 ms 2504 KB Output is correct
10 Correct 4659 ms 2504 KB Output is correct
11 Correct 7 ms 2392 KB Output is correct
12 Correct 164 ms 2508 KB Output is correct
13 Correct 166 ms 2504 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2408 KB Output is correct
8 Correct 4515 ms 2504 KB Output is correct
9 Correct 4622 ms 2504 KB Output is correct
10 Correct 4659 ms 2504 KB Output is correct
11 Correct 7 ms 2392 KB Output is correct
12 Correct 164 ms 2508 KB Output is correct
13 Correct 166 ms 2504 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2408 KB Output is correct
8 Correct 4515 ms 2504 KB Output is correct
9 Correct 4622 ms 2504 KB Output is correct
10 Correct 4659 ms 2504 KB Output is correct
11 Correct 7 ms 2392 KB Output is correct
12 Correct 164 ms 2508 KB Output is correct
13 Correct 166 ms 2504 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2408 KB Output is correct
8 Correct 4515 ms 2504 KB Output is correct
9 Correct 4622 ms 2504 KB Output is correct
10 Correct 4659 ms 2504 KB Output is correct
11 Correct 7 ms 2392 KB Output is correct
12 Correct 164 ms 2508 KB Output is correct
13 Correct 166 ms 2504 KB Output is correct
14 Incorrect 1 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -