Submission #716182

#	Time	Username	Problem	Language	Result	Execution time	Memory
716182		Nhoksocqt1	Ancient Machine (JOI21_ancient_machine)	C++17	70 / 100	74 ms	8920 KiB

Anna

#ifndef Nhoksocqt1
    #include "Anna.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

int prv[MAXN], nxt[MAXN];
int pos[MAXN], tmp[MAXN], val[MAXN];
bool dx[MAXN];

#ifdef Nhoksocqt1

vector<int> sendedMessage;

void Send(int x) {
    sendedMessage.push_back(x);
}

void Remove(int d) {
    cout << "REMOVE AT POS: " << d << '\n';
}

#endif // Nhoksocqt1

void Anna(int n, vector<char> S) {
    int l(0), r(n - 1);
    for (int i = 0; i < n; ++i)
        val[i] = (S[i] != 'X') + (S[i] == 'Z');

    while(l <= r && val[l] != 0)
        ++l;

    while(r >= l && val[r] != 2)
        --r;

    for (int i = 0; i < n; ++i)
        dx[i] = 0;

    if(l <= r)
        dx[l] = dx[r] = 1;

    for (int j = l + 1; j < r; ++j) {
        while(j < r && val[j] == val[j + 1])
            ++j;

        if(j < r && val[j] == 2)
            dx[j] = 1;
    }

    for (int i = 0; i < n; ++i)
        Send(dx[i]);
}

#ifdef Nhoksocqt1

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    freopen("JOI21MACHINE.inp", "r", stdin);
    freopen("JOI21MACHINE.out", "w", stdout);

    vector<char> s;
    int n;

    cin >> n;
    s.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        //s[i] = Random(0, 2) + 'X'; cout << s[i];
    }
    //cout << '\n';

    Anna(n, s);
    cout << "SENDED MESSAGES: "; for (int it : sendedMessage) cout << it; cout << '\n';
    Bruno(n, sz(sendedMessage), sendedMessage);
    return 0;
}

#endif // Nhoksocqt1

Bruno

#ifndef Nhoksocqt1
    #include "Bruno.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 100005;

int prv[MAXN], nxt[MAXN];
int pos[MAXN], tmp[MAXN], val[MAXN];
bool dx[MAXN];

#ifdef Nhoksocqt1

vector<int> sendedMessage;

void Send(int x) {
    sendedMessage.push_back(x);
}

void Remove(int d) {
    cout << "REMOVE AT POS: " << d << '\n';
}

#endif // Nhoksocqt1

void Bruno(int N, int L, vector<int> A) {
    for (int i = 0; i < N; ++i)
        dx[i] = A[i];

    int fl(-1), last(-1);
    for (int i = 0; i < N; ++i) {
        if(dx[i]) {
            last = i + 1;
            break;
        }

        Remove(i);
    }

    fl = last;
    if(last < 0)
        return;

    for (int i = last; i < N; ++i) {
        if(dx[i]) {
            for (int j = i - 1; j >= last; --j)
                Remove(j);

            Remove(i);
            last = i + 1;
        }
    }

    Remove(fl - 1);
    for (int i = last; i < N; ++i)
        Remove(i);
}

#ifdef Nhoksocqt1

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    freopen("JOI21MACHINE.inp", "r", stdin);
    freopen("JOI21MACHINE.out", "w", stdout);

    vector<char> s;
    int n;

    cin >> n;
    s.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        //s[i] = Random(0, 2) + 'X'; cout << s[i];
    }
    //cout << '\n';

    Anna(n, s);
    cout << "SENDED MESSAGES: "; for (int it : sendedMessage) cout << it; cout << '\n';
    Bruno(n, sz(sendedMessage), sendedMessage);
    return 0;
}

#endif // Nhoksocqt1

• Subtask 1: 5 / 5
• Subtask 2: 65 / 95