제출 #708775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708775		yuuhi	Ancient Machine (JOI21_ancient_machine)	C++17	30 / 100	187 ms	15860 KiB

Anna

#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) ;
        }
    }
}

Bruno

#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 / 5
• Subtask 2: 25 / 95