oj.uz

Submission #935587

# Submission time Handle Problem Language Result Execution time Memory
935587 2024-02-29T09:32:10 Z Nhoksocqt1 Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 42 ms 8384 KB 
#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;

ll fibo[100];
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

string trans(int l, int r) {
    string S;
    for (int i = l; i <= r; ++i)
        S.push_back(dx[i] + '0');

    ll sum(0);
    for (int i = 0; i < sz(S); ++i) {
        if(S[i] == '1')
            sum += fibo[63 - i];
    }

    S.clear();
    while(sum > 0) {
        S.push_back(sum % 2 + '0');
        sum /= 2;
    }

    reverse(S.begin(), S.end());
    return S;
}

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) {
        Send(0);
        return;
    }

    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 && j > l + 1 && val[j] == 2)
            dx[j] = 1;
    }

    fibo[0] = 1, fibo[1] = 2;
    for (int i = 2; i <= 64; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

    for (int i = 0; i < n; i += 64) {
        string S = trans(i, min(i + 63, n - 1));
        while(sz(S) < 45)
            S = '0' + S;

        for (int it = 0; it < sz(S); ++it)
            Send(S[it] - '0');
    }
}

#ifdef Nhoksocqt1

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

    freopen("ancient_machine.inp", "r", stdin);
    freopen("ancient_machine.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';

    fibo[0] = 1, fibo[1] = 2;
    for (int i = 2; i <= 64; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

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

#endif // Nhoksocqt1

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

ll fibo[100];
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

string trans(int l, int r) {
    string S;
    for (int i = l; i <= r; ++i)
        S.push_back(dx[i] + '0');

    ll sum(0);
    for (int i = 0; i < sz(S); ++i) {
        if(S[i] == '1')
            sum += fibo[63 - i];
    }

    S.clear();
    while(sum > 0) {
        S.push_back(sum % 2 + '0');
        sum /= 2;
    }

    reverse(S.begin(), S.end());
    return S;
}

void Bruno(int N, int L, vector<int> A) {
    if(sz(A) == 1) {
        for (int i = 0; i < N; ++i)
            Remove(i);

        return;
    }

    fibo[0] = 1, fibo[1] = 2;
    for (int i = 2; i <= 64; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

    for (int i = 0; i < N; i += 64) {
        ll sum(0);
        for (int j = 0; j < 45; ++j)
            sum += (ll(A[(i / 64) * 45 + j]) << (44 - j));

        for (int j = 63; j >= 0 && i + 63 - j < N; --j) {
            if(sum < fibo[j]) {
                dx[i + (63 - j)] = 0;
                continue;
            }

            dx[i + (63 - j)] = 1;
            sum -= fibo[j];
        }
    }

    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("ancient_machine.inp", "r", stdin);
    freopen("ancient_machine.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';

    fibo[0] = 1, fibo[1] = 2;
    for (int i = 2; i <= 64; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 796 KB Output is correct
2 Correct 0 ms 796 KB Output is correct
3 Correct 0 ms 796 KB Output is correct
4 Correct 0 ms 800 KB Output is correct
5 Correct 1 ms 784 KB Output is correct
6 Correct 0 ms 784 KB Output is correct
7 Correct 0 ms 796 KB Output is correct
8 Correct 0 ms 796 KB Output is correct
9 Correct 0 ms 796 KB Output is correct
10 Correct 0 ms 796 KB Output is correct
11 Correct 2 ms 780 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Partially correct 39 ms 8340 KB Partially correct
2 Partially correct 42 ms 8248 KB Partially correct
3 Incorrect 33 ms 8384 KB Wrong Answer [6]
4 Halted 0 ms 0 KB -