oj.uz

Submission #708740

# Submission time Handle Problem Language Result Execution time Memory
708740 2023-03-12T08:54:32 Z yuuhi Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 466 ms 16364 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) ;
        }
    }
    for (int i = 0 ; i < n ; ++ i) s.insert(i) ;

    auto goodRemove = [&](int x) {
        auto itl = l.lower_bound(x) ;
        auto itr = r.upper_bound(x) ;
        if (itl == l.begin() || itr == r.end()) return 0 ;
        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) {
        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) ;
    };

    queue< int > q ;
    for (int i : cand) {
//        cout << i << " " << goodRemove(i) << "\n" ;
        if (goodRemove(i)) q.push(i) ;
    }
    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 (goodRemove(*it)) q.push(*it) ;
        }
        if (it != cand.begin()) {
            it -- ;
            if (goodRemove(*it)) q.push(*it) ;
        }
    }
    for (int i = 0 ; i < n ; ++ i) if (!erased[i]) Erase(i) ;
}
/*
5
X Y X Y Z
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 291 ms 14528 KB Partially correct
2 Partially correct 291 ms 14680 KB Partially correct
3 Partially correct 313 ms 14620 KB Partially correct
4 Incorrect 466 ms 16364 KB Wrong Answer [6]
5 Halted 0 ms 0 KB -