Submission #40421276 - AtCoder Regular Contest 159

Contest Duration: 2023-04-08 21:00:00+0900 - 2023-04-08 23:00:00+0900 (local time) (120 minutes) Back to Home

Submission #40421276

Source Code Expand

#include <bits/stdc++.h>

using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
template<i64 P>
struct MLong {
    i64 x;
    constexpr MLong() : x{} {}
    constexpr MLong(i64 x) : x{norm(x % getMod())} {}
    
    static i64 Mod;
    constexpr static i64 getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_) {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const {
        return x;
    }
    explicit constexpr operator i64() const {
        return x;
    }
    constexpr MLong operator-() const {
        MLong res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MLong inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MLong &operator*=(MLong rhs) & {
        x = mul(x, rhs.x, getMod());
        return *this;
    }
    constexpr MLong &operator+=(MLong rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MLong &operator-=(MLong rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MLong &operator/=(MLong rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs) {
        MLong res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
        i64 v;
        is >> v;
        a = MLong(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
i64 MLong<0LL>::Mod = 1;

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

template<>
int MInt<0>::Mod = 1;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 998244353;
using Z = MInt<P>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N;
    std::cin >> N;
    
    std::vector<int> a(2 * N);
    for (int i = 0; i < 2 * N; i++) {
        std::cin >> a[i];
        a[i]--;
    }
    
    std::vector<Z> dp(N + 1);
    dp[0] = 1;
    
    std::vector<std::vector<int>> p(2 * N);
    for (int i = 0; i < 2 * N; i++) {
        p[a[i]].push_back(i / 2 + 1);
        p[a[i]].push_back(i / 2 + 1);
    }
    
    std::vector<int> cnt(2 * N);
    std::vector<std::vector<int>> f(N + 1);
    for (int i = 0; i < 2 * N; i++) {
        for (int j = p[i].size() - 1, k = N, x = j; j >= 0; j--) {
            f[p[i][j]].push_back(i);
            k = std::min(k, p[i][j]);
            if (k < 0) {
                continue;
            }
            while (true) {
                while (x >= 0 && p[i][x] > k) {
                    x--;
                }
                if (x == -1 || p[i][x] < k) {
                    break;
                }
                k--;
            }
            f[k].push_back(i);
            k--;
        }
        for (int j = 0, k = 0, x = j; j < p[i].size(); j++) {
            k = std::max(k, p[i][j]);
            if (k > N) {
                continue;
            }
            while (true) {
                while (x < p[i].size() && p[i][x] < k) {
                    x++;
                }
                if (x >= p[i].size() || p[i][x] > k) {
                    break;
                }
                k++;
            }
            if (k <= N) {
                f[k].push_back(i);
            }
            k++;
        }
    }
    
    Z sum = 0;
    std::vector<std::map<int, Z>> g(2 * N);
    std::vector<int> vis(2 * N, -1);
    for (int i = 0; i <= N; i++) {
        // std::cerr << "i : " << i << ", sum : " << sum << "\n";
        if (i == 0) {
            dp[i] = 1;
        } else {
            cnt[a[2 * i - 2]] += 1;
            cnt[a[2 * i - 1]] += 1;
            for (auto x : f[i]) {
                if (vis[x] == 2 * i) {
                    continue;
                }
                vis[x] = 2 * i;
                int c = (a[2 * i - 2] == x) + (a[2 * i - 1] == x);
                // std::cerr << x << " " << c << "\n";
                if (c == 0) {
                    sum += g[x][cnt[x] - i];
                }
                if (c == 2) {
                    sum -= g[x][cnt[x] - i - 1];
                }
            }
            dp[i] = sum;
        }
        for (auto x : f[i]) {
            if (vis[x] == 2 * i + 1) {
                continue;
            }
            vis[x] = 2 * i + 1;
            g[x][cnt[x] - i] += dp[i];
        }
        sum += dp[i];
    }
    std::cout << dp[N] << "\n";
    
    return 0;
}

Submission Info

Submission Time	2023-04-08 22:11:38+0900
Task	F - Good Division
User	jiangly
Language	C++ (GCC 9.2.1)
Score	900
Code Size	8249 Byte
Status	AC
Exec Time	2926 ms
Memory	359460 KiB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:264:41: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  264 |         for (int j = 0, k = 0, x = j; j < p[i].size(); j++) {
      |                                       ~~^~~~~~~~~~~~~
./Main.cpp:270:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  270 |                 while (x < p[i].size() && p[i][x] < k) {
      |                        ~~^~~~~~~~~~~~~
./Main.cpp:273:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  273 |                 if (x >= p[i].size() || p[i][x] > k) {
      |                     ~~^~~~~~~~~~~~~~

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

900 / 900

Status

× 4

× 88

Set Name	Test Cases
Sample	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_srnd_00.txt, 01_srnd_01.txt, 01_srnd_02.txt, 01_srnd_03.txt, 01_srnd_04.txt, 01_srnd_05.txt, 01_srnd_06.txt, 01_srnd_07.txt, 01_srnd_08.txt, 01_srnd_09.txt, 02_min_00.txt, 02_min_01.txt, 02_min_02.txt, 02_min_03.txt, 02_min_04.txt, 02_min_05.txt, 02_min_06.txt, 02_min_07.txt, 02_min_08.txt, 03_rnd_00.txt, 03_rnd_01.txt, 03_rnd_02.txt, 03_rnd_03.txt, 03_rnd_04.txt, 03_rnd_05.txt, 03_rnd_06.txt, 03_rnd_07.txt, 03_rnd_08.txt, 03_rnd_09.txt, 04_sqrt_00.txt, 04_sqrt_01.txt, 04_sqrt_02.txt, 04_sqrt_03.txt, 04_sqrt_04.txt, 04_sqrt_05.txt, 04_sqrt_06.txt, 04_sqrt_07.txt, 04_sqrt_08.txt, 04_sqrt_09.txt, 04_sqrt_10.txt, 05_one_00.txt, 05_one_01.txt, 05_one_02.txt, 06_two_00.txt, 06_two_01.txt, 06_two_02.txt, 06_two_03.txt, 06_two_04.txt, 06_two_05.txt, 07_few_00.txt, 07_few_01.txt, 07_few_02.txt, 07_few_03.txt, 07_few_04.txt, 07_few_05.txt, 07_few_06.txt, 07_few_07.txt, 07_few_08.txt, 08_many_00.txt, 08_many_01.txt, 08_many_02.txt, 08_many_03.txt, 08_many_04.txt, 08_many_05.txt, 08_many_06.txt, 08_many_07.txt, 08_many_08.txt, 09_perm_00.txt, 09_perm_01.txt, 09_perm_02.txt, 09_perm_03.txt, 10_pow_00.txt, 10_pow_01.txt, 10_pow_02.txt, 10_pow_03.txt, 10_pow_04.txt, 10_pow_05.txt, 10_pow_06.txt, 10_pow_07.txt, 11_special_00.txt, 11_special_01.txt, 11_special_02.txt, 11_special_03.txt, 11_special_04.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	5 ms	3492 KiB
00_sample_01.txt	AC	2 ms	3512 KiB
00_sample_02.txt	AC	2 ms	3456 KiB
00_sample_03.txt	AC	2 ms	3548 KiB
01_srnd_00.txt	AC	2 ms	3536 KiB
01_srnd_01.txt	AC	2 ms	3456 KiB
01_srnd_02.txt	AC	2 ms	3504 KiB
01_srnd_03.txt	AC	1 ms	3544 KiB
01_srnd_04.txt	AC	2 ms	3504 KiB
01_srnd_05.txt	AC	2 ms	3484 KiB
01_srnd_06.txt	AC	2 ms	3548 KiB
01_srnd_07.txt	AC	2 ms	3552 KiB
01_srnd_08.txt	AC	2 ms	3548 KiB
01_srnd_09.txt	AC	3 ms	3512 KiB
02_min_00.txt	AC	2 ms	3444 KiB
02_min_01.txt	AC	2 ms	3584 KiB
02_min_02.txt	AC	2 ms	3588 KiB
02_min_03.txt	AC	2 ms	3520 KiB
02_min_04.txt	AC	2 ms	3440 KiB
02_min_05.txt	AC	1 ms	3444 KiB
02_min_06.txt	AC	2 ms	3524 KiB
02_min_07.txt	AC	2 ms	3600 KiB
02_min_08.txt	AC	2 ms	3548 KiB
03_rnd_00.txt	AC	2009 ms	347532 KiB
03_rnd_01.txt	AC	1493 ms	317732 KiB
03_rnd_02.txt	AC	1913 ms	349412 KiB
03_rnd_03.txt	AC	1544 ms	317520 KiB
03_rnd_04.txt	AC	2185 ms	343000 KiB
03_rnd_05.txt	AC	1503 ms	317508 KiB
03_rnd_06.txt	AC	2124 ms	343068 KiB
03_rnd_07.txt	AC	1455 ms	318340 KiB
03_rnd_08.txt	AC	2094 ms	344052 KiB
03_rnd_09.txt	AC	1572 ms	317444 KiB
04_sqrt_00.txt	AC	2337 ms	313524 KiB
04_sqrt_01.txt	AC	2363 ms	314028 KiB
04_sqrt_02.txt	AC	2366 ms	314840 KiB
04_sqrt_03.txt	AC	2335 ms	314816 KiB
04_sqrt_04.txt	AC	2365 ms	315564 KiB
04_sqrt_05.txt	AC	2360 ms	312372 KiB
04_sqrt_06.txt	AC	2342 ms	312376 KiB
04_sqrt_07.txt	AC	2348 ms	312860 KiB
04_sqrt_08.txt	AC	2360 ms	313788 KiB
04_sqrt_09.txt	AC	2340 ms	314372 KiB
04_sqrt_10.txt	AC	2394 ms	315064 KiB
05_one_00.txt	AC	388 ms	145760 KiB
05_one_01.txt	AC	392 ms	145644 KiB
05_one_02.txt	AC	391 ms	145760 KiB
06_two_00.txt	AC	285 ms	129264 KiB
06_two_01.txt	AC	287 ms	129200 KiB
06_two_02.txt	AC	284 ms	129280 KiB
06_two_03.txt	AC	282 ms	129084 KiB
06_two_04.txt	AC	284 ms	129304 KiB
06_two_05.txt	AC	451 ms	139196 KiB
07_few_00.txt	AC	597 ms	155460 KiB
07_few_01.txt	AC	757 ms	183664 KiB
07_few_02.txt	AC	1114 ms	217340 KiB
07_few_03.txt	AC	1221 ms	240188 KiB
07_few_04.txt	AC	1483 ms	249400 KiB
07_few_05.txt	AC	1562 ms	271220 KiB
07_few_06.txt	AC	1655 ms	265124 KiB
07_few_07.txt	AC	1754 ms	286816 KiB
07_few_08.txt	AC	1697 ms	270580 KiB
08_many_00.txt	AC	2070 ms	316188 KiB
08_many_01.txt	AC	2846 ms	340488 KiB
08_many_02.txt	AC	2086 ms	316156 KiB
08_many_03.txt	AC	2926 ms	340420 KiB
08_many_04.txt	AC	2139 ms	315800 KiB
08_many_05.txt	AC	2897 ms	340452 KiB
08_many_06.txt	AC	2173 ms	316132 KiB
08_many_07.txt	AC	2920 ms	340740 KiB
08_many_08.txt	AC	2139 ms	315884 KiB
09_perm_00.txt	AC	1749 ms	359460 KiB
09_perm_01.txt	AC	1744 ms	359460 KiB
09_perm_02.txt	AC	1414 ms	320100 KiB
09_perm_03.txt	AC	1451 ms	320040 KiB
10_pow_00.txt	AC	2292 ms	300036 KiB
10_pow_01.txt	AC	2338 ms	309892 KiB
10_pow_02.txt	AC	2857 ms	335728 KiB
10_pow_03.txt	AC	2282 ms	314220 KiB
10_pow_04.txt	AC	2205 ms	315340 KiB
10_pow_05.txt	AC	2149 ms	316168 KiB
10_pow_06.txt	AC	2876 ms	341220 KiB
10_pow_07.txt	AC	1477 ms	317796 KiB
11_special_00.txt	AC	1440 ms	284548 KiB
11_special_01.txt	AC	1438 ms	286392 KiB
11_special_02.txt	AC	1535 ms	289684 KiB
11_special_03.txt	AC	1183 ms	258420 KiB
11_special_04.txt	AC	1664 ms	317508 KiB