Submission #68602985 - AtCoder Regular Contest 204 (Div. 1)

Contest Duration: 2025-08-17 21:00:00+0900 - 2025-08-17 23:30:00+0900 (local time) (150 minutes) Back to Home

Submission #68602985

Source Code Expand

//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
/*
░░░░░░░█▐▓▓░████▄▄▄█▀▄▓▓▓▌█
░░░░░▄█▌▀▄▓▓▄▄▄▄▀▀▀▄▓▓▓▓▓▌█
░░░▄█▀▀▄▓█▓▓▓▓▓▓▓▓▓▓▓▓▀░▓▌█
░░█▀▄▓▓▓███▓▓▓███▓▓▓▄░░▄▓▐█▌
░█▌▓▓▓▀▀▓▓▓▓███▓▓▓▓▓▓▓▄▀▓▓▐█
▐█▐██▐░▄▓▓▓▓▓▀▄░▀▓▓▓▓▓▓▓▓▓▌█▌
█▌███▓▓▓▓▓▓▓▓▐░░▄▓▓███▓▓▓▄▀▐█
█▐█▓▀░░▀▓▓▓▓▓▓▓▓▓██████▓▓▓▓▐█
▌▓▄▌▀░▀░▐▀█▄▓▓██████████▓▓▓▌█▌
▌▓▓▓▄▄▀▀▓▓▓▀▓▓▓▓▓▓▓▓█▓█▓█▓▓▌█▌
█▐▓▓▓▓▓▓▄▄▄▓▓▓▓▓▓█▓█▓█▓█▓▓▓▐█ йоу
 */
#include <iostream>
#include "queue"
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "random"
#ifndef __APPLE__
#include "bits/stdc++.h"
#endif
#define all(x) x.begin(), x.end()
using namespace std;

typedef bitset<150001> bts;
void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < p.size(); ++i) {
        cin >> p[i];
        p[i]--;
    }
    int res = 0;
    vector<int> ar;
    vector<int> seen(p.size());
    vector<int> evens(n + 1);
    for (int i = 0; i < p.size(); ++i) {
        if (seen[i] == 0) {
            vector<int> clc;
            int v = i;
            while (seen[v] == 0) {
                seen[v] = 1;
                clc.push_back(v);
                v = p[v];
            }
            ar.push_back(clc.size());
            if (clc.size() % 2 == 0)
                evens[clc.size() / 2]++;
            //cout << clc.size() << ' ';
        }
    }
    bts canget;
    canget[0] = 1;
    for (int i = 0; i < evens.size(); ++i) {
        int dg = evens[i];
        for (int j = 0; (1<<(j+1)) - 1 <= evens[i]; ++j) {
            canget |= (canget << (i<<j));
            dg = evens[i] - (1<<(j+1)) + 1;
        }
        canget |= (canget << (dg * i));
    }
    vector<int> prvcn(n + 1, -1);
    prvcn[0] = 0;
    for (int i = 1; i <= n; ++i) {
        if (canget[i]) {
            //cerr << i << '\n';
            prvcn[i] = i;
        } else {
            prvcn[i] = prvcn[i-1];
        }
    }
    auto cmp = [](int a, int b) {
        if (a % 2 != b % 2)
            return a % 2 < b % 2;
        if (a % 2 == 0)
            return a < b;
        else
            return a > b;
    };
    sort(all(ar), cmp);
    int q;
    cin >> q;
    vector<int> ans(q);
    vector<array<int, 3>> quer(q);
    for (int i = 0; i < q; ++i) {
        int a, b, stepa;
        cin >> a >> b >> stepa;
        quer[i] = {a, b, i};
    }
    sort(all(quer));
    int pr = 0;
    vector<int> put0(ar.size());
    int ind = 0;
    int one1 = 0, one2 = 0;
    bool frst = 1;
    int answ = 0;
    int smdlt = 0;

    for (auto [val0, val1, indans] : quer) {
        int dlt2 = val0 - pr;
        pr = val0;//0 2 0 1 2
        for (int iqqq = 0; iqqq < dlt2; ++iqqq) {
            int dlt = 1;
            if (frst) {
                while (ind < ar.size()) {
                    int trg = ar[ind] / 2 - put0[ind];
                    int c = min(dlt, trg);
                    if (c != 0) {
                        for (int i = 0; i < c; ++i) {
                            answ += 2;
                            dlt--;
                            smdlt++;
                            put0[ind]++;
                            if (ar[ind] == 2) {
                                one2++;
                            } else {
                                if (put0[ind] == 1) {
                                    one1 += 2;
                                } else {
                                    one2++;
                                }
                                if (put0[ind] == ar[ind]/2) {
                                    if (ar[ind]/2 * 2 == ar[ind]) {
                                        one2++;
                                        one1 -= 2;
                                    }
                                }
                            }
                        }
                    } else {
                        if (trg == 0)
                            ind++;
                        else
                            break;
                    }
                }
                if (ind == ar.size()) {
                    frst = 0;
                    ind = 0;
                }
            }
            if (!frst) {
                while (ind < ar.size()) {
                    int trg = (ar[ind]+1) / 2 - put0[ind];
                    int c = min(dlt, trg);
                    if (c != 0) {
                        if (ar[ind] != 1) {
                            dlt--;
                            smdlt++;
                            put0[ind]++;
                            one1 -= 2;
                            one2++;
                            answ++;
                        } else {
                            dlt--;
                            smdlt++;
                            put0[ind]++;
                            answ++;
                        }
                    } else {
                        if (trg == 0)
                            ind++;
                        else
                            break;
                    }
                }
            }
        }
        //    cerr << answ << ' ' << one1 << ' ' << one2 << ' ' << smdlt << '\n';
        if (frst and ar[ind] % 2 == 0) {
            int c = min(val1, val0);
            int c2 = val0 - prvcn[c];
            int apl = prvcn[c] * 4 + c2 * 2;
            if (c2 != 0) {
                apl += min(c2+1, (val1-prvcn[c]));
                apl += min(c2-1, (val1-prvcn[c]));
            }
            ans[indans] = apl;
        } else {
            int cor = answ;
            int c = min(val1, one2);
            val1 -= c;
            cor += c * 2;
            c = min(val1, one1);
            cor += c;
            ans[indans] = cor;
        }
    }
    for (auto i : ans)
        cout << i << '\n';

}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

/*
2 2 50
3 4 0 1 1 0 1 1
4 5 1 2 1 1 1 2
 1 5 3 2 4 1 5 3 2 4

 9
1 6 7 3 5 8 9 2 4
1
5 3 1

 9
1 6 7 3 5 8 9 2 4
1
5 3 1
 */

Submission Info

Submission Time	2025-08-17 23:44:19+0900
Task	C - Maximize Sum of Mex
User	SomethingNew
Language	C++ 20 (gcc 12.2)
Score	900
Code Size	7006 Byte
Status	AC
Exec Time	342 ms
Memory	13688 KiB

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:42:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   42 |     for (int i = 0; i < p.size(); ++i) {
      |                     ~~^~~~~~~~~~
Main.cpp:50:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   50 |     for (int i = 0; i < p.size(); ++i) {
      |                     ~~^~~~~~~~~~
Main.cpp:67:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   67 |     for (int i = 0; i < evens.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:118:28: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  118 |                 while (ind < ar.size()) {
      |                        ~~~~^~~~~~~~~~~
Main.cpp:150:25: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  150 |                 if (ind == ar.size()) {
      |                     ~~~~^~~~~~~~~~~~
Main.cpp:156:28: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  156 |                 while (ind < ar.size()) {
      |                        ~~~~^~~~~~~~~~~
Main.cpp:46:9: warning: unused variable ‘res’ [-Wunused-variable]
   46 |     int res = 0;
      |         ^~~

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

900 / 900

Status

× 3

× 51

Set Name	Test Cases
Sample	01-sample-01.txt, 01-sample-02.txt, 01-sample-03.txt
All	01-sample-01.txt, 01-sample-02.txt, 01-sample-03.txt, 02-small-01.txt, 02-small-02.txt, 02-small-03.txt, 02-small-04.txt, 02-small-05.txt, 02-small-06.txt, 02-small-07.txt, 02-small-08.txt, 02-small-09.txt, 02-small-10.txt, 03-random-01.txt, 03-random-02.txt, 03-random-03.txt, 03-random-04.txt, 03-random-05.txt, 03-random-06.txt, 03-random-07.txt, 03-random-08.txt, 03-random-09.txt, 03-random-10.txt, 04-divide-01.txt, 04-divide-02.txt, 04-divide-03.txt, 04-divide-04.txt, 04-divide-05.txt, 04-divide-06.txt, 04-divide-07.txt, 04-divide-08.txt, 04-divide-09.txt, 04-divide-10.txt, 05-even-divide-01.txt, 05-even-divide-02.txt, 05-even-divide-03.txt, 05-even-divide-04.txt, 05-even-divide-05.txt, 05-even-divide-06.txt, 05-even-divide-07.txt, 05-even-divide-08.txt, 05-even-divide-09.txt, 05-even-divide-10.txt, 06-even-triangular-divide-01.txt, 06-even-triangular-divide-02.txt, 07-large-cycle-01.txt, 07-large-cycle-02.txt, 08-odd-triangular-divide-01.txt, 08-odd-triangular-divide-02.txt, 09-triangular-divide-01.txt, 09-triangular-divide-02.txt

Case Name	Status	Exec Time	Memory
01-sample-01.txt	AC	1 ms	3576 KiB
01-sample-02.txt	AC	1 ms	3520 KiB
01-sample-03.txt	AC	1 ms	3376 KiB
02-small-01.txt	AC	1 ms	3472 KiB
02-small-02.txt	AC	1 ms	3660 KiB
02-small-03.txt	AC	1 ms	3488 KiB
02-small-04.txt	AC	1 ms	3532 KiB
02-small-05.txt	AC	1 ms	3412 KiB
02-small-06.txt	AC	1 ms	3656 KiB
02-small-07.txt	AC	1 ms	3656 KiB
02-small-08.txt	AC	1 ms	3520 KiB
02-small-09.txt	AC	1 ms	3384 KiB
02-small-10.txt	AC	1 ms	3536 KiB
03-random-01.txt	AC	326 ms	12612 KiB
03-random-02.txt	AC	323 ms	12268 KiB
03-random-03.txt	AC	332 ms	13512 KiB
03-random-04.txt	AC	324 ms	12528 KiB
03-random-05.txt	AC	327 ms	12580 KiB
03-random-06.txt	AC	338 ms	12384 KiB
03-random-07.txt	AC	336 ms	12896 KiB
03-random-08.txt	AC	325 ms	12812 KiB
03-random-09.txt	AC	331 ms	12868 KiB
03-random-10.txt	AC	326 ms	12280 KiB
04-divide-01.txt	AC	330 ms	12524 KiB
04-divide-02.txt	AC	327 ms	12492 KiB
04-divide-03.txt	AC	332 ms	12520 KiB
04-divide-04.txt	AC	325 ms	12556 KiB
04-divide-05.txt	AC	329 ms	12576 KiB
04-divide-06.txt	AC	332 ms	12488 KiB
04-divide-07.txt	AC	330 ms	12428 KiB
04-divide-08.txt	AC	326 ms	12488 KiB
04-divide-09.txt	AC	327 ms	12524 KiB
04-divide-10.txt	AC	332 ms	12544 KiB
05-even-divide-01.txt	AC	338 ms	13688 KiB
05-even-divide-02.txt	AC	342 ms	13248 KiB
05-even-divide-03.txt	AC	338 ms	13040 KiB
05-even-divide-04.txt	AC	336 ms	12916 KiB
05-even-divide-05.txt	AC	335 ms	12784 KiB
05-even-divide-06.txt	AC	335 ms	12848 KiB
05-even-divide-07.txt	AC	336 ms	12772 KiB
05-even-divide-08.txt	AC	334 ms	12820 KiB
05-even-divide-09.txt	AC	335 ms	12764 KiB
05-even-divide-10.txt	AC	335 ms	12492 KiB
06-even-triangular-divide-01.txt	AC	336 ms	12428 KiB
06-even-triangular-divide-02.txt	AC	323 ms	12228 KiB
07-large-cycle-01.txt	AC	334 ms	12428 KiB
07-large-cycle-02.txt	AC	330 ms	12876 KiB
08-odd-triangular-divide-01.txt	AC	333 ms	12520 KiB
08-odd-triangular-divide-02.txt	AC	330 ms	12476 KiB
09-triangular-divide-01.txt	AC	332 ms	12584 KiB
09-triangular-divide-02.txt	AC	325 ms	12228 KiB