Submission #1153700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153700		RiverFlow	Ancient Machine (JOI21_ancient_machine)	C++20	5 / 100	46 ms	2500 KiB

Anna

#include <bits/stdc++.h>

// #define LOCAL

#ifndef LOCAL
#include "Anna.h"
#endif

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

namespace {

int variable_example = 0;

}


#ifdef LOCAL
vector<int> sent;
void Send(int a) {
    assert(a == 0 or a == 1);
    sent.push_back(a);
}
#endif

void Anna(int n, vector<char> s) {
    for(int i = 0; i < n; ++i) {
        int x = (s[i] == 'X' ? 0 : (s[i] == 'Y' ? 1 : 2));
        FOD(j, 1, 0) Send(1 & x >> j);
    }
}


#ifdef LOCAL

int main() {
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
    int n;
    cin >> n;
    vector<char> s(n);
    for(int i = 0; i < n; ++i) {
        cin >> s[i];
    }
    Anna(n, s);
    cout << n << ' ' << sz(sent) << nl;
    for(int x : sent) cout << x << ' ';
    return 0;
}

#endif

Bruno

#include <bits/stdc++.h>

// #define LOCAL
#ifndef LOCAL
#include "Bruno.h"
#endif

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b or a==-1) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

namespace {

int variable_example = 0;

int FunctionExample(int P) { return 1 - P; }

}  // namespace


#ifdef LOCAL
void Remove(int d) {
    cout << d << nl;
}
#endif

#define MASK(i) (1 << (i))

void Bruno(int n, int l, vector<int> a) {
    vector<int> v;
    for(int i = 0; i < l; i += 2) {
        v.push_back(a[i] * 2 + a[i + 1]);
    }
//    for(int x : v) cout << x << ' '; cout << nl;
    if (n > 18) return ;
    vector<int> dp(1 << n, -1), trace(1 << n, 0);
    dp[(1 << n) - 1] = 0;
    for(int mask = (1 << n) - 1; mask > 0; --mask) {
        vector<int> p;
        FOR(i, 0, n - 1) if (1 & mask >> i) p.push_back(i);
        for(int i = 0; i < sz(p); ++i) {
            if (maxi(dp[mask ^ MASK(p[i])],
            dp[mask] + (i > 0 and i < sz(p) - 1 and  v[p[i-1]] == 0
            and v[p[i]] == 1 and v[p[i+1]] == 2)))
                trace[mask ^ MASK(p[i])] = p[i];
        }
    }
    vector<int> ord;
    int st = 0;
    while (st != (1 << n) - 1) {
        int k = trace[st];
        ord.push_back(k);
        st ^= (1 << k);
    }
    reverse(all(ord));
    for(int x : ord) Remove(x);


//    vec<vec<int>> nxt(n + 1, vec<int> (3, -1));
//    for(int i = n - 1; i >= 0; --i) {
//        FOR(j, 0, 2) nxt[i][j] = nxt[i + 1][j];
//        nxt[i][v[i]] = i;
//    }
//    vector<int> pos;
//    pos.push_back(-1);
//    int t = 0, c = 0;
//    while (true) {
//        if (nxt[t][c] == -1) {
//            break ;
//        }
//        t = nxt[t][c];
//        c = (c + 1) % 3;
//        pos.push_back(t);
//    }
//    while (sz(pos) % 3 != 1) pos.pop_back();
//    pos.push_back(n);
//    for(int i = 0; i < sz(pos) - 1; ++i) {
//        for(int j = pos[i] + 1; j < pos[i + 1]; ++j)
//            Remove(j);
//    }
//    for(int i = 1; i < sz(pos) - 1; i += 3) {
//        Remove(pos[i + 1]);
//        Remove(pos[i]);
//        Remove(pos[i + 2]);
//    }
}


#ifdef LOCAL

int main() {
    freopen(task".out", "r", stdin);
//    freopen(task".out", "w", stdout);
    int n, l;
    cin >> n >> l;
    vector<int> a(l);
    for(int i = 0; i < l; ++i) cin >> a[i];
    Bruno(n, l, a);
}

#endif


/*     Let the river flows naturally     */

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