Submission #708768

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
708768	2023-03-12T09:18:17 Z	yuuhi	Ancient Machine (JOI21_ancient_machine)	C++17	5 / 100	149 ms	14860 KB

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) ;
        }
    }
    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 ;
        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	0 ms	508 KB	Output is correct
2	Correct	0 ms	516 KB	Output is correct
3	Correct	0 ms	516 KB	Output is correct
4	Correct	1 ms	520 KB	Output is correct
5	Correct	0 ms	520 KB	Output is correct
6	Correct	0 ms	516 KB	Output is correct
7	Correct	1 ms	524 KB	Output is correct
8	Correct	0 ms	508 KB	Output is correct
9	Correct	0 ms	504 KB	Output is correct
10	Correct	0 ms	504 KB	Output is correct
11	Correct	0 ms	508 KB	Output is correct

Subtask #2

0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	149 ms	14636 KB	Partially correct
2	Partially correct	137 ms	14756 KB	Partially correct
3	Partially correct	141 ms	14752 KB	Partially correct
4	Incorrect	135 ms	14860 KB	Wrong Answer [6]
5	Halted	0 ms	0 KB	-