oj.uz

Submission #708775

# Submission time Handle Problem Language Result Execution time Memory
708775 2023-03-12T09:34:37 Z yuuhi Ancient Machine (JOI21_ancient_machine) C++17
30 / 100
 187 ms 15860 KB 
#include<bits/stdc++.h>
#include "Anna.h"

#define f first
#define s second
#define double long double
#define _size(x) ((int)((x).size()))

using namespace std ;

typedef pair< int , int > ii ;

void Anna (int n , vector< char > s) {
    for (int i = 0 ; i < n ; ++ i) {
        if (s[i] == 'X') {
            Send(0) ;
            Send(0) ;
        }
        else if (s[i] == 'Y') {
            Send(0) ;
            Send(1) ;
        }
        else {
            Send(1) ;
            Send(0) ;
        }
    }
}

#include<bits/stdc++.h>
#include "Bruno.h"

#define f first
#define s second
#define double long double
#define _size(x) ((int)((x).size()))

using namespace std ;

typedef pair< int , int > ii ;

void Bruno (int n , int L , vector< int > b) {
    vector< int > a(n) ;
    for (int i = 0 ; i < n ; ++ i) {
        a[i] = (b[i << 1] << 1) | b[i << 1 | 1] ;
    }

    vector< int > erased(n , 0) ;
    set< int > cand ;
    set< int > l , r , s ;
    for (int i = 0 ; i < n ; ++ i) {
        if (a[i] == 1) {
            int j = i ;
            while (j + 1 < n && a[j + 1] == 1) j ++ ;
            cand.insert(i) ;
            i = j ;
        }
        else if (a[i] == 0) {
            l.insert(i) ;
        }
        else {
            r.insert(i) ;
        }
    }
//    cout << _size(cand) << "\n" ;
    for (int i = 0 ; i < n ; ++ i) s.insert(i) ;

    auto goodRemove = [&](int x) {
        if (cand.find(x) == cand.end()) return 0 ;
        auto itl = l.lower_bound(x) ;
        auto itr = r.upper_bound(x) ;
        if (itl == l.begin() || itr == r.end()) return 0 ;
        itl -- ;
        int ok = 1 ;
        auto it = cand.lower_bound(x) ;
        if (it != cand.begin()) {
            it -- ;
            if (*itl < *it) ok = 0 ;
            it ++ ;
        }
//        cout << ok << "\n" ;
        it ++ ;
        if (it != cand.end()) {
            if (*itr > *it) ok = 0 ;
        }
//        cout << ok << "\n" ;
        return ok ;
    };

    auto Erase = [&](int x) {
        if (erased[x]) return ;
        erased[x] = 1 ;
        s.erase(s.find(x)) ;
        if (a[x] == 0) l.erase(l.find(x)) ;
        if (a[x] == 2) r.erase(r.find(x)) ;
        auto it = cand.find(x) ;
        if (it != cand.end()) cand.erase(it) ;
        Remove(x) ;
//        cout << x << "\n" ;
    };

    auto goRemove = [&](int x) {
        if (cand.find(x) == cand.end()) return ;
        auto itl = l.lower_bound(x) ;
        auto itr = r.upper_bound(x) ;
        int L = *(-- itl) , R = *itr ;
        while (1) {
            auto it = s.lower_bound(x) ;
            if (it == s.begin()) break ;
            it -- ;
            if (*it > L) Erase(*it) ;
            else break ;
        }
        while (1) {
            auto it = s.upper_bound(x) ;
            if (it == s.end()) break ;
            if (*it < R) Erase(*it) ;
            else break ;
        }
        Erase(x) ;
    };

    vector< int > inq(n , 0) ;
    queue< int > q ;
    for (int i : cand) {
//        cout << i << " " << goodRemove(i) << "\n" ;
        if (goodRemove(i)) {
            q.push(i) ;
            inq[i] = 1 ;
        }
    }
    while (!q.empty()) {
        int x = q.front() ; q.pop() ;
//        cout << x << "\n" ;
        goRemove(x) ;
        auto it = cand.upper_bound(x) ;
        if (it != cand.end()) {
            if (!inq[*it] && goodRemove(*it)) {
                q.push(*it) ;
                inq[*it] = 1 ;
            }
        }
        if (it != cand.begin()) {
            it -- ;
            if (!inq[*it] && goodRemove(*it)) {
                q.push(*it) ;
                inq[*it] = 1 ;
            }
        }
    }
    for (int i = 0 ; i < n ; ++ i) if (!erased[i]) Erase(i) ;
}
/*
10
X Y Y X Z Y X Z Y Z
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 520 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 1 ms 516 KB Output is correct
6 Correct 1 ms 520 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 1 ms 516 KB Output is correct
10 Correct 1 ms 520 KB Output is correct
11 Correct 1 ms 524 KB Output is correct

Subtask #2
25.0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 146 ms 15184 KB Partially correct
2 Partially correct 160 ms 15108 KB Partially correct
3 Partially correct 162 ms 15148 KB Partially correct
4 Partially correct 142 ms 15036 KB Partially correct
5 Partially correct 161 ms 15132 KB Partially correct
6 Partially correct 146 ms 15060 KB Partially correct
7 Partially correct 174 ms 15268 KB Partially correct
8 Partially correct 158 ms 15204 KB Partially correct
9 Partially correct 147 ms 15088 KB Partially correct
10 Partially correct 156 ms 15228 KB Partially correct
11 Partially correct 146 ms 15164 KB Partially correct
12 Partially correct 151 ms 15012 KB Partially correct
13 Partially correct 161 ms 15016 KB Partially correct
14 Partially correct 147 ms 15012 KB Partially correct
15 Partially correct 143 ms 15476 KB Partially correct
16 Partially correct 147 ms 15044 KB Partially correct
17 Partially correct 135 ms 14860 KB Partially correct
18 Partially correct 125 ms 10776 KB Partially correct
19 Partially correct 136 ms 15016 KB Partially correct
20 Partially correct 186 ms 15632 KB Partially correct
21 Partially correct 187 ms 15708 KB Partially correct
22 Partially correct 104 ms 10948 KB Partially correct
23 Partially correct 176 ms 15860 KB Partially correct
24 Partially correct 149 ms 15692 KB Partially correct
25 Partially correct 114 ms 10960 KB Partially correct
26 Partially correct 122 ms 10924 KB Partially correct
27 Partially correct 102 ms 10980 KB Partially correct
28 Partially correct 113 ms 10952 KB Partially correct
29 Partially correct 109 ms 10940 KB Partially correct
30 Partially correct 104 ms 10776 KB Partially correct
31 Partially correct 117 ms 10856 KB Partially correct
32 Partially correct 148 ms 14488 KB Partially correct
33 Partially correct 153 ms 14440 KB Partially correct