QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#49488#1261. Invckiseki#AC ✓223ms90028kbC++2.4kb2022-09-21 16:53:382022-09-21 16:53:39

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-21 16:53:39]
  • 评测
  • 测评结果:AC
  • 用时:223ms
  • 内存:90028kb
  • [2022-09-21 16:53:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;

uint32_t dp[maxn][maxn * maxn];
uint32_t pre[maxn * maxn];
void build(int x) {
    for (int i = 0; i < maxn * maxn; i++) {
        pre[i] = dp[x][i];
        if (i >= 2) pre[i] += pre[i - 2];
    }
}

auto brute(int n) {
    vector<int> p(n, -1);
    vector<int> res(n * (n-1) / 2 + 1);
    const auto dfs = [&](auto self, int i) {
        if (i == n) {
            int cnt = 0;
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < x; y++) {
                    if (p[y] > p[x])
                        ++cnt;
                }
            }
            // cerr << "cnt = " << cnt << endl;
            // for (int x = 0; x < n; x++)
            //     cerr << p[x]+1 << ' ';
            // cerr << endl;
            ++res[cnt];
            return;
        }
        if (p[i] != -1) {
            self(self, i + 1);
            return;
        }
        p[i] = i;
        self(self, i + 1);
        p[i] = -1;
        for (int j = i + 1; j < n; j++) {
            if (p[j] != -1) continue;
            p[i] = j;
            p[j] = i;
            self(self, i + 1);
            p[i] = p[j] = -1;
        }
    };
    dfs(dfs, 0);
    for (int i = 0; i <= n*(n-1)/2; i++) {
        cout << res[i] << ' ';
    }
    cout << '\n';
    return res;
}

uint32_t query(int r, int l) {
    if (r < 0)
        return 0;
    else if (l - 2 < 0)
        return pre[r];
    else
        return pre[r] - pre[l - 2];
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, K;
    cin >> n >> K;

    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i*(i-1)/2; j++)
            dp[i][j] = dp[i-1][j];
        if (i>=2) {
            build(i-2);
            for (int j = 0; j <= i*(i-1)/2; j++) {
                dp[i][j] += query(j - 1, j - 1 - (i-2) * 2);
                // for (int k = 0; k <= i-2; k++) {
                //     int jj = j - (i-2-k)*2 - 1;
                //     if (jj >= 0)
                //         dp[i][j] += dp[i-2][jj];
                // }
            }
        }
    }

    // cout << dp[n][K] << '\n';
    cout << dp[n][K] % 2 << '\n';
    // for (int j = 0; j <= n*(n-1)/2; j++) {
    //     cout << dp[n][j] << ' ';
    // }
    // cout << '\n';
    // auto R = brute(n);

    // for (int j = 0; j <= n*(n-1)/2; j++) {
    //     assert (dp[n][j] == R[j]);
    // }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4724kb

input:

4 1

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 2ms
memory: 4588kb

input:

10 21

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 213ms
memory: 87912kb

input:

500 124331

output:

0

result:

ok answer is '0'

Test #4:

score: 0
Accepted
time: 13ms
memory: 4700kb

input:

20 122

output:

1

result:

ok answer is '1'

Test #5:

score: 0
Accepted
time: 46ms
memory: 5704kb

input:

100 999

output:

0

result:

ok answer is '0'

Test #6:

score: 0
Accepted
time: 199ms
memory: 88000kb

input:

500 100001

output:

1

result:

ok answer is '1'

Test #7:

score: 0
Accepted
time: 2ms
memory: 4636kb

input:

5 0

output:

1

result:

ok answer is '1'

Test #8:

score: 0
Accepted
time: 2ms
memory: 4576kb

input:

5 1

output:

0

result:

ok answer is '0'

Test #9:

score: 0
Accepted
time: 4ms
memory: 4640kb

input:

5 2

output:

1

result:

ok answer is '1'

Test #10:

score: 0
Accepted
time: 5ms
memory: 4728kb

input:

5 3

output:

1

result:

ok answer is '1'

Test #11:

score: 0
Accepted
time: 5ms
memory: 4636kb

input:

5 4

output:

0

result:

ok answer is '0'

Test #12:

score: 0
Accepted
time: 5ms
memory: 4652kb

input:

5 5

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 2ms
memory: 4564kb

input:

5 6

output:

0

result:

ok answer is '0'

Test #14:

score: 0
Accepted
time: 2ms
memory: 4720kb

input:

5 7

output:

1

result:

ok answer is '1'

Test #15:

score: 0
Accepted
time: 1ms
memory: 4576kb

input:

5 8

output:

1

result:

ok answer is '1'

Test #16:

score: 0
Accepted
time: 2ms
memory: 4508kb

input:

5 9

output:

0

result:

ok answer is '0'

Test #17:

score: 0
Accepted
time: 5ms
memory: 4576kb

input:

5 10

output:

1

result:

ok answer is '1'

Test #18:

score: 0
Accepted
time: 202ms
memory: 88012kb

input:

500 73732

output:

1

result:

ok answer is '1'

Test #19:

score: 0
Accepted
time: 192ms
memory: 87592kb

input:

499 21121

output:

1

result:

ok answer is '1'

Test #20:

score: 0
Accepted
time: 181ms
memory: 87592kb

input:

499 100000

output:

0

result:

ok answer is '0'

Test #21:

score: 0
Accepted
time: 170ms
memory: 87420kb

input:

499 62262

output:

1

result:

ok answer is '1'

Test #22:

score: 0
Accepted
time: 181ms
memory: 87420kb

input:

499 23432

output:

1

result:

ok answer is '1'

Test #23:

score: 0
Accepted
time: 201ms
memory: 87908kb

input:

500 12321

output:

0

result:

ok answer is '0'

Test #24:

score: 0
Accepted
time: 206ms
memory: 87992kb

input:

500 60000

output:

1

result:

ok answer is '1'

Test #25:

score: 0
Accepted
time: 205ms
memory: 88792kb

input:

498 7498

output:

1

result:

ok answer is '1'

Test #26:

score: 0
Accepted
time: 222ms
memory: 88992kb

input:

498 76111

output:

1

result:

ok answer is '1'

Test #27:

score: 0
Accepted
time: 129ms
memory: 54444kb

input:

414 41414

output:

1

result:

ok answer is '1'

Test #28:

score: 0
Accepted
time: 173ms
memory: 56552kb

input:

422 42224

output:

1

result:

ok answer is '1'

Test #29:

score: 0
Accepted
time: 143ms
memory: 31388kb

input:

333 33333

output:

1

result:

ok answer is '1'

Test #30:

score: 0
Accepted
time: 188ms
memory: 89952kb

input:

500 51515

output:

1

result:

ok answer is '1'

Test #31:

score: 0
Accepted
time: 158ms
memory: 47788kb

input:

393 21222

output:

1

result:

ok answer is '1'

Test #32:

score: 0
Accepted
time: 223ms
memory: 89440kb

input:

500 124750

output:

1

result:

ok answer is '1'

Test #33:

score: 0
Accepted
time: 186ms
memory: 89272kb

input:

500 124749

output:

1

result:

ok answer is '1'

Test #34:

score: 0
Accepted
time: 192ms
memory: 90028kb

input:

500 0

output:

1

result:

ok answer is '1'

Test #35:

score: 0
Accepted
time: 197ms
memory: 89968kb

input:

500 1

output:

1

result:

ok answer is '1'

Test #36:

score: 0
Accepted
time: 3ms
memory: 5688kb

input:

1 0

output:

1

result:

ok answer is '1'