Submission #35295719

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#include <set>

using namespace std;

int main() {
    int n;
    set<int> used;
    int spare = 0;
    vector<int> as(0, n);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        if (used.find(a) == used.end()) {
            as.push_back(a);
            used.insert(a);
        } else {
            spare++;
        }
    }
    sort(as.begin(), as.end());
    int last_idx = as.size();
    int idx = 0;
    int ans = 0;
    for (int i = 1; ; i++) {
        if (idx >= last_idx) {
            if (spare >= 2) {
                spare -= 2;
                ans++;
                continue;
            } else {
                break;
            }
        }
        //cout << i << "," << idx << "," << last_idx << endl;
        if (as[idx] == i) {
            ans++;
            idx+=1;
        } else {
            int nokori = last_idx - idx;
            if (spare >= 2) {
                spare -= 2;
                ans++;
            } else if (spare == 1 && nokori >= 1) {
                last_idx--;
                spare--;
                ans+=1;
            } else if (nokori >= 2) {
                last_idx-=2;
                ans+=1;
            } else {
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Manga
User tomoya
Language C++ (Clang 10.0.0)
Score 300
Code Size 1462 Byte
Status AC
Exec Time 421 ms
Memory 18160 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 29
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_one_00.txt, 01_one_01.txt, 01_one_02.txt, 02_srnd_00.txt, 02_srnd_01.txt, 02_srnd_02.txt, 02_srnd_03.txt, 02_srnd_04.txt, 02_srnd_05.txt, 02_srnd_06.txt, 03_rnd_00.txt, 03_rnd_01.txt, 03_rnd_02.txt, 03_rnd_03.txt, 04_max_00.txt, 04_max_01.txt, 04_max_02.txt, 05_same_00.txt, 05_same_01.txt, 05_same_02.txt, 05_same_03.txt, 05_same_04.txt, 05_same_05.txt, 06_concat_00.txt, 06_concat_01.txt, 06_concat_02.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 8 ms 3088 KiB
00_sample_01.txt AC 2 ms 3060 KiB
00_sample_02.txt AC 3 ms 3016 KiB
01_one_00.txt AC 2 ms 3160 KiB
01_one_01.txt AC 2 ms 3192 KiB
01_one_02.txt AC 2 ms 3008 KiB
02_srnd_00.txt AC 2 ms 3044 KiB
02_srnd_01.txt AC 2 ms 3020 KiB
02_srnd_02.txt AC 2 ms 3176 KiB
02_srnd_03.txt AC 2 ms 3012 KiB
02_srnd_04.txt AC 2 ms 3056 KiB
02_srnd_05.txt AC 2 ms 3148 KiB
02_srnd_06.txt AC 2 ms 3092 KiB
03_rnd_00.txt AC 414 ms 17192 KiB
03_rnd_01.txt AC 416 ms 17308 KiB
03_rnd_02.txt AC 421 ms 17348 KiB
03_rnd_03.txt AC 415 ms 17208 KiB
04_max_00.txt AC 267 ms 18040 KiB
04_max_01.txt AC 264 ms 18088 KiB
04_max_02.txt AC 399 ms 17872 KiB
05_same_00.txt AC 151 ms 3168 KiB
05_same_01.txt AC 147 ms 3144 KiB
05_same_02.txt AC 148 ms 3008 KiB
05_same_03.txt AC 151 ms 3024 KiB
05_same_04.txt AC 146 ms 3144 KiB
05_same_05.txt AC 147 ms 3144 KiB
06_concat_00.txt AC 255 ms 12900 KiB
06_concat_01.txt AC 254 ms 12952 KiB
06_concat_02.txt AC 268 ms 18160 KiB