提出 #43546828
ソースコード 拡げる
// LUOGU_RID: 115425625
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 998244353
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define lowbit(x) x & (-x)
#define PII pair<int, int>
#define MP make_pair
#define VI vector<int>
#define VII vector<int>::iterator
#define EB emplace_back
#define SI set<int>
#define SII set<int>::iterator
#define QI queue<int>
using namespace std;
template<typename T> void chkmn(T &a, const T &b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T &b) { (a < b) && (a = b); }
int inc(const int &a, const int &b) { return a + b >= MOD ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
int res = 1;
while(k)
{
if(k & 1) Mul(res, x);
Sqr(x), k >>= 1;
}
return res;
}
const int N = 505;
const int M = 11;
int n, d, a[N];
int f[N][1 << M], ans;
int maxS;
int main()
{
scanf("%d %d", &n, &d);
maxS = 1 << (2 * d + 1);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
f[0][0] = 1;
for(int i = 1; i <= n; ++i)
{
for(int S = 0; S < maxS; ++S)
{
int T = S >> 1;
for(int j = -d; j <= d; ++j)
{
if(i + j < 1 || i + j > n) continue;
if((T >> (d + j)) & 1) continue;
if(a[i] != -1 && a[i] != i + j) continue;
Inc(f[i][T | (1 << (d + j))], f[i - 1][S]);
}
}
}
printf("%d\n", f[n][(1 << (d + 1)) - 1]);
return 0;
}
提出情報
| 提出日時 | |
|---|---|
| 問題 | C - Almost Sorted |
| ユーザ | Schucking_Sattin |
| 言語 | C++ (GCC 9.2.1) |
| 得点 | 600 |
| コード長 | 1783 Byte |
| 結果 | AC |
| 実行時間 | 58 ms |
| メモリ | 7664 KiB |
コンパイルエラー
./Main.cpp: In function ‘int main()’:
./Main.cpp:44:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
44 | scanf("%d %d", &n, &d);
| ~~~~~^~~~~~~~~~~~~~~~~
./Main.cpp:47:8: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
47 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
ジャッジ結果
| セット名 | Sample | All | ||||
|---|---|---|---|---|---|---|
| 得点 / 配点 | 0 / 0 | 600 / 600 | ||||
| 結果 |
|
|
| セット名 | テストケース |
|---|---|
| Sample | sample1.txt, sample2.txt, sample3.txt |
| All | empty_1_0.txt, empty_1_1.txt, empty_2_0.txt, empty_2_1.txt, empty_3_0.txt, empty_3_1.txt, empty_4_0.txt, empty_4_1.txt, empty_5_0.txt, empty_5_1.txt, rndSwap_1_3.txt, rndSwap_1_5.txt, rndSwap_1_8.txt, rndSwap_2_3.txt, rndSwap_2_5.txt, rndSwap_2_8.txt, rndSwap_3_3.txt, rndSwap_3_5.txt, rndSwap_3_8.txt, rndSwap_4_3.txt, rndSwap_4_5.txt, rndSwap_4_8.txt, rndSwap_5_3.txt, rndSwap_5_5.txt, rndSwap_5_8.txt, rnd_1_1.txt, rnd_1_2.txt, rnd_2_1.txt, rnd_2_2.txt, rnd_3_1.txt, rnd_3_2.txt, rnd_4_1.txt, rnd_4_2.txt, rnd_5_1.txt, rnd_5_2.txt, sample1.txt, sample2.txt, sample3.txt, smalls_1.txt, smalls_2.txt, zero.txt |
| ケース名 | 結果 | 実行時間 | メモリ |
|---|---|---|---|
| empty_1_0.txt | AC | 9 ms | 5604 KiB |
| empty_1_1.txt | AC | 5 ms | 5504 KiB |
| empty_2_0.txt | AC | 7 ms | 5584 KiB |
| empty_2_1.txt | AC | 7 ms | 5552 KiB |
| empty_3_0.txt | AC | 6 ms | 5604 KiB |
| empty_3_1.txt | AC | 6 ms | 5576 KiB |
| empty_4_0.txt | AC | 17 ms | 5516 KiB |
| empty_4_1.txt | AC | 15 ms | 5472 KiB |
| empty_5_0.txt | AC | 52 ms | 7592 KiB |
| empty_5_1.txt | AC | 53 ms | 7620 KiB |
| rndSwap_1_3.txt | AC | 5 ms | 5592 KiB |
| rndSwap_1_5.txt | AC | 6 ms | 5436 KiB |
| rndSwap_1_8.txt | AC | 3 ms | 5380 KiB |
| rndSwap_2_3.txt | AC | 7 ms | 5508 KiB |
| rndSwap_2_5.txt | AC | 5 ms | 5564 KiB |
| rndSwap_2_8.txt | AC | 5 ms | 5560 KiB |
| rndSwap_3_3.txt | AC | 7 ms | 5400 KiB |
| rndSwap_3_5.txt | AC | 7 ms | 5492 KiB |
| rndSwap_3_8.txt | AC | 9 ms | 5556 KiB |
| rndSwap_4_3.txt | AC | 18 ms | 5376 KiB |
| rndSwap_4_5.txt | AC | 25 ms | 5684 KiB |
| rndSwap_4_8.txt | AC | 16 ms | 5624 KiB |
| rndSwap_5_3.txt | AC | 53 ms | 7632 KiB |
| rndSwap_5_5.txt | AC | 54 ms | 7584 KiB |
| rndSwap_5_8.txt | AC | 55 ms | 7664 KiB |
| rnd_1_1.txt | AC | 6 ms | 5724 KiB |
| rnd_1_2.txt | AC | 5 ms | 5596 KiB |
| rnd_2_1.txt | AC | 5 ms | 5548 KiB |
| rnd_2_2.txt | AC | 5 ms | 5640 KiB |
| rnd_3_1.txt | AC | 7 ms | 5628 KiB |
| rnd_3_2.txt | AC | 7 ms | 5720 KiB |
| rnd_4_1.txt | AC | 17 ms | 5348 KiB |
| rnd_4_2.txt | AC | 15 ms | 5708 KiB |
| rnd_5_1.txt | AC | 51 ms | 7536 KiB |
| rnd_5_2.txt | AC | 51 ms | 7484 KiB |
| sample1.txt | AC | 2 ms | 3776 KiB |
| sample2.txt | AC | 3 ms | 3728 KiB |
| sample3.txt | AC | 5 ms | 3892 KiB |
| smalls_1.txt | AC | 2 ms | 3740 KiB |
| smalls_2.txt | AC | 5 ms | 5004 KiB |
| zero.txt | AC | 58 ms | 7656 KiB |