Submission #947207


Source Code Expand

#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <random>
#include <list>
#include <numeric>
using namespace std;
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<int, ll> i_ll;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
#define rep(i, N) for (int i = 0; i < (int)(N); i++)
#define pb push_back
 
int INF = INT_MAX / 10;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int pow_mod(ll x, ll n, int M) {
	ll ans = 1;
	for (; n; n>>=1) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
	}
	return ans;
}

ll inv_mod(int x, int p) {
	return pow_mod(x, p - 2, p);
}

struct bit {
	vector<ll> v;
	bit(int n) : v(n + 1) {}
	ll sum(int i) {
		ll res = 0;
		for (; i > 0; i -= i & -i) res += v[i];
		return res;
	}
	void add(int i, ll x) {
		for (i++; i < v.size(); i += i & -i) v[i] += x;
	}
};

int main() {
	int N; cin >> N;
	vector<int> a(N);
	rep(i, N) {
		scanf("%d", &a[i]);
		a[i]--;
	}
	reverse(a.begin(), a.end());
	bit unko(N), unko2(N);
	rep(i, N) if (a[i] != -1) unko.add(a[i], 1);
	rep(i, N) if (unko.sum(i + 1) - unko.sum(i) == 0) unko2.add(i, 1);
	int kakutei = unko.sum(N), mikakutei = unko2.sum(N);
	int hatena = 0;
	ll hoge = 0, fact = 1, ans = 0;
	bit b(N);
	rep(i, N) {
		int x = a[i];
		ll z = 0;
		if (x == -1) {
			z = (hatena * inv_mod(2, MOD) + hoge) % MOD;
			hatena++;
		}
		else {
			hoge = (hoge + (unko2.sum(N) - unko2.sum(x)) * inv_mod(mikakutei, MOD)) % MOD;
			z = (b.sum(x) + unko2.sum(x) * inv_mod(mikakutei, MOD) % MOD * hatena) % MOD;
			b.add(x, 1);
		}
		ans = (ans + z * fact) % MOD;
		fact = fact * (i + 1) % MOD;
	}
	ans = (ans + 1) % MOD;
	for (int i = 1; i <= mikakutei; i++)
		ans = ans * i % MOD;
	ans = (ans + MOD) % MOD;
	cout << ans << endl;
}

Submission Info

Submission Time
Task E - Encyclopedia of Permutations
User sugim48
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 2287 Byte
Status AC
Exec Time 701 ms
Memory 13952 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:73:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 500 / 500 700 / 700
Status
AC × 5
AC × 33
AC × 58
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt
Subtask 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt, 2_051.txt, 2_052.txt, 2_053.txt, 2_054.txt, 2_055.txt, 2_056.txt, 2_057.txt
Case Name Status Exec Time Memory
0_000.txt AC 3 ms 256 KB
0_001.txt AC 3 ms 256 KB
0_002.txt AC 3 ms 256 KB
0_003.txt AC 2 ms 256 KB
0_004.txt AC 3 ms 256 KB
1_005.txt AC 3 ms 256 KB
1_006.txt AC 3 ms 256 KB
1_007.txt AC 3 ms 256 KB
1_008.txt AC 5 ms 384 KB
1_009.txt AC 4 ms 256 KB
1_010.txt AC 5 ms 384 KB
1_011.txt AC 4 ms 256 KB
1_012.txt AC 5 ms 384 KB
1_013.txt AC 3 ms 256 KB
1_014.txt AC 5 ms 384 KB
1_015.txt AC 4 ms 256 KB
1_016.txt AC 5 ms 384 KB
1_017.txt AC 3 ms 256 KB
1_018.txt AC 6 ms 384 KB
1_019.txt AC 4 ms 256 KB
1_020.txt AC 6 ms 384 KB
1_021.txt AC 4 ms 256 KB
1_022.txt AC 6 ms 384 KB
1_023.txt AC 5 ms 256 KB
1_024.txt AC 6 ms 384 KB
1_025.txt AC 3 ms 256 KB
1_026.txt AC 6 ms 384 KB
1_027.txt AC 4 ms 256 KB
1_028.txt AC 5 ms 384 KB
1_029.txt AC 6 ms 384 KB
1_030.txt AC 6 ms 384 KB
1_031.txt AC 6 ms 384 KB
1_032.txt AC 5 ms 384 KB
2_033.txt AC 356 ms 13952 KB
2_034.txt AC 178 ms 7040 KB
2_035.txt AC 397 ms 13952 KB
2_036.txt AC 365 ms 12800 KB
2_037.txt AC 441 ms 13952 KB
2_038.txt AC 383 ms 12288 KB
2_039.txt AC 479 ms 13952 KB
2_040.txt AC 238 ms 7040 KB
2_041.txt AC 515 ms 13952 KB
2_042.txt AC 98 ms 2816 KB
2_043.txt AC 562 ms 13952 KB
2_044.txt AC 360 ms 9216 KB
2_045.txt AC 593 ms 13952 KB
2_046.txt AC 571 ms 13312 KB
2_047.txt AC 630 ms 13952 KB
2_048.txt AC 271 ms 6272 KB
2_049.txt AC 663 ms 13952 KB
2_050.txt AC 430 ms 9216 KB
2_051.txt AC 653 ms 13952 KB
2_052.txt AC 591 ms 12544 KB
2_053.txt AC 356 ms 13952 KB
2_054.txt AC 701 ms 13952 KB
2_055.txt AC 619 ms 13952 KB
2_056.txt AC 617 ms 13952 KB
2_057.txt AC 511 ms 13952 KB