oj.uz

답안 #935629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935629 2024-02-29T09:59:20 Z Nhoksocqt1 Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 47 ms 8504 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[110];
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[62 - 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] = 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] = 1;
    }

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

    for (int i = 0; i <= n; i += 63) {
        string S = trans(i, min(i + 62, n));
        while(sz(S) < 44)
            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 <= 63; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

    for (int i = 1; i <= 63; ++i) {
        int x = log2(fibo[i]) + 1;
        cout << ((int(1e5) + i) / i * x) << ' ' << x << ' ' << fibo[i] << '\n';
    }

    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[110];
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[62 - 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 <= 80; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

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

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

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

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

    for (int i = fx + 2; i <= N; ++i)
        dx[i - 1] = dx[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("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 <= 63; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

    for (int i = 1; i <= 63; ++i) {
        int x = log2(fibo[i]) + 1;
        cout << ((int(1e5) + i) / i * x) << ' ' << x << ' ' << fibo[i] << '\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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 796 KB Output is correct
2 Correct 0 ms 796 KB Output is correct
3 Correct 0 ms 800 KB Output is correct
4 Correct 0 ms 784 KB Output is correct
5 Correct 0 ms 784 KB Output is correct
6 Correct 1 ms 784 KB Output is correct
7 Correct 0 ms 784 KB Output is correct
8 Correct 1 ms 780 KB Output is correct
9 Correct 1 ms 784 KB Output is correct
10 Correct 0 ms 792 KB Output is correct
11 Correct 0 ms 792 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 8236 KB Output is correct
2 Correct 40 ms 8380 KB Output is correct
3 Correct 39 ms 8404 KB Output is correct
4 Correct 40 ms 8336 KB Output is correct
5 Correct 38 ms 8336 KB Output is correct
6 Correct 38 ms 8260 KB Output is correct
7 Correct 38 ms 8292 KB Output is correct
8 Correct 39 ms 8288 KB Output is correct
9 Correct 38 ms 8324 KB Output is correct
10 Correct 40 ms 8504 KB Output is correct
11 Correct 38 ms 8372 KB Output is correct
12 Correct 38 ms 8292 KB Output is correct
13 Correct 47 ms 8344 KB Output is correct
14 Correct 42 ms 8336 KB Output is correct
15 Correct 39 ms 8232 KB Output is correct
16 Correct 39 ms 8268 KB Output is correct
17 Correct 33 ms 7184 KB Output is correct
18 Correct 32 ms 7308 KB Output is correct
19 Correct 33 ms 7152 KB Output is correct
20 Correct 40 ms 8304 KB Output is correct
21 Correct 39 ms 8240 KB Output is correct
22 Correct 44 ms 8224 KB Output is correct
23 Correct 38 ms 8248 KB Output is correct
24 Correct 36 ms 8504 KB Output is correct
25 Correct 35 ms 7324 KB Output is correct
26 Correct 32 ms 7108 KB Output is correct
27 Correct 34 ms 7228 KB Output is correct
28 Correct 33 ms 7228 KB Output is correct
29 Correct 32 ms 7292 KB Output is correct
30 Correct 33 ms 7240 KB Output is correct
31 Correct 33 ms 7304 KB Output is correct
32 Correct 38 ms 8240 KB Output is correct
33 Correct 38 ms 8236 KB Output is correct