Submission #1197682


Source Code Expand

Copy
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

/*int n,p[10100],q[10100],r[10100],x[10100];
set<VI> hs;
bool valid() {
	int pl=r[0],pr=r[0];
	rep(i,1,n) {
		if (pl<r[i]&&r[i]<pr) return 0;
		if (r[i]<pl) pl=r[i]; else if (r[i]>pr) pr=r[i];
	}
	return 1;
}
void dfs(int x) {
	if (x==n) {
		rep(i,0,n) printf("%d ",r[i]); puts("");
		assert(valid()==hs.count(VI(r,r+n)));
	} else {
		rep(i,n-x,n+x+1) {
			r[x]=i;
			dfs(x+1);
		}
	}
}*/
const int N=110;
int n,a[N],dp[N][N][N],ret;
map<int,int> hs;
void upd(int &a,int b) {
	a+=b; if (a>=mod) a-=mod;
}
int main() {
	scanf("%d",&n);
	rep(i,1,2*n) scanf("%d",a+i),hs[a[i]]=0;
	sort(a+1,a+2*n);
	int id=0;
	for (auto &x:hs) x.se=++id;
	rep(i,1,2*n) a[i]=hs[a[i]];
	dp[0][1][0]=1;
	rep(i,0,n) rep(j,1,a[n+i]-a[n-i]+2) rep(k,0,j) if (dp[i][j][k]) {
		int nj=j,nk=k;
		if (a[n+i+1]!=a[n+i]) nj++;
		if (a[n-i-1]!=a[n-i]) nj++,nk++;
		if (i<n-1) {
			rep(l,0,nj) upd(dp[i+1][nj-max(abs(l-nk)-1,0)][l-max(l-nk-1,0)],dp[i][j][k]);
		} else {
			upd(ret,dp[i][j][k]);
		}
//		printf("%d %d %d %d\n",i,j,k,dp[i][j][k]);
	}
	printf("%d\n",ret);
}

Submission Info

Submission Time
Task F - Prefix Median
User apiad
Language C++14 (GCC 5.4.1)
Score 2000
Code Size 1742 Byte
Status
Exec Time 28 ms
Memory 3200 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:54:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:55:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  rep(i,1,2*n) scanf("%d",a+i),hs[a[i]]=0;
                                         ^

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 2000 / 2000 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt
Case Name Status Exec Time Memory
00_example_01.txt 1 ms 256 KB
00_example_02.txt 1 ms 256 KB
00_example_03.txt 1 ms 384 KB
01.txt 28 ms 3200 KB
02.txt 21 ms 3200 KB
03.txt 4 ms 640 KB
04.txt 2 ms 512 KB
05.txt 2 ms 384 KB
06.txt 10 ms 1024 KB
07.txt 28 ms 3200 KB
08.txt 2 ms 512 KB
09.txt 28 ms 3200 KB
10.txt 1 ms 256 KB
11.txt 1 ms 384 KB
12.txt 2 ms 384 KB
13.txt 8 ms 896 KB
14.txt 13 ms 1024 KB
15.txt 1 ms 256 KB
16.txt 9 ms 2944 KB
17.txt 1 ms 256 KB
18.txt 1 ms 256 KB
19.txt 1 ms 256 KB
20.txt 1 ms 384 KB
21.txt 1 ms 384 KB
22.txt 1 ms 256 KB
23.txt 2 ms 512 KB
24.txt 1 ms 384 KB
25.txt 2 ms 512 KB
26.txt 3 ms 640 KB
27.txt 1 ms 384 KB
28.txt 9 ms 2944 KB
29.txt 1 ms 384 KB
30.txt 2 ms 512 KB
31.txt 1 ms 256 KB
32.txt 2 ms 512 KB
33.txt 1 ms 256 KB
34.txt 2 ms 512 KB
35.txt 5 ms 2816 KB
36.txt 1 ms 256 KB
37.txt 8 ms 2944 KB
38.txt 2 ms 512 KB
39.txt 2 ms 512 KB
40.txt 1 ms 384 KB
41.txt 4 ms 768 KB
42.txt 11 ms 3072 KB
43.txt 1 ms 384 KB
44.txt 11 ms 2944 KB
45.txt 1 ms 256 KB
46.txt 1 ms 256 KB
47.txt 1 ms 384 KB
48.txt 4 ms 768 KB
49.txt 6 ms 896 KB
50.txt 1 ms 256 KB
51.txt 2 ms 2432 KB