Submission #888971

#	Time	Username	Problem	Language	Result	Execution time	Memory
888971		thunopro	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++14	10 / 100	4659 ms	2508 KiB

festival2

#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 (stderr)

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 27
• Subtask 4: 0 / 14
• Subtask 5: 0 / 36
• Subtask 6: 0 / 13