oj.uz

Submission #585499

# Submission time Handle Problem Language Result Execution time Memory
585499 2022-06-29T02:50:40 Z 79brue Ancient Machine (JOI21_ancient_machine) C++17
100 / 100
 56 ms 9568 KB 
#include "Anna.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace nAnna{
    int n;
    int arr[100005];
    int first0=-1, last2=-1, last1=-1;

    bool bits[200005];
    ll bitSeq[2002];

    ll DP[100][2];

    ll calc(vector<bool> v){
        assert(v.size() == 63);
        ll val = 0;
        for(int i=0; i<63; i++){
            if(v[i] == 1) val += DP[63-i][0];
        }
        return val;
    }

    void Anna(int N, vector<char> _s){
        n = N;
        for(int i=0; i<n; i++) arr[i] = _s[i] - 'X';

        for(int i=0; i<n; i++) if(arr[i] == 0){
            first0 = i;
            break;
        }
        if(first0 == -1 || first0 >= n-2) return;

        DP[0][0] = 1;
        for(int i=1; i<=63; i++){
            DP[i][1] = DP[i-1][0];
            DP[i][0] = DP[i-1][0] + DP[i-1][1];
        }

        bool firstBit = (arr[first0+1] == 2);
        bits[first0] = 1;
        for(int i=first0+2; i<n; i++) if(arr[i] == 2 && arr[i+1] != 2) bits[i] = 1;

        for(int i=0; i<n; i+=63){
            bitSeq[i/63] = calc(vector<bool> (bits+i, bits+i+63));
        }
        Send(firstBit);
        for(int i=0; i<(n+62)/63; i++) for(int j=0; j<44; j++) Send((bitSeq[i] >> j) & 1);
    }
}

void Anna(int N, vector<char> S){
    return nAnna::Anna(N, S);
}

#include "Bruno.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace nBruno{
    int n, k;
    int arr[100002];
    bool removed[100002];
    vector<int> stk;

    int last1;
    ll decode[100002];
    bool bits[100002];

    void remove(int x){
        #ifdef TEST
        printf("Remove %d\n", x);
        #endif // TEST
        Remove(x);
        removed[x] = 1;
    }

    ll DP[102][2];

    void Bruno(int _n, int _l, vector<int> _vec){
        n = _n, k = _l;
        if(!k){
            for(int i=0; i<n; i++) Remove(i);
            return;
        }
        for(int i=0; i<k; i++) arr[i] = _vec[i];

        DP[0][0] = 1;
        for(int i=1; i<=63; i++){
            DP[i][1] = DP[i-1][0];
            DP[i][0] = DP[i-1][0] + DP[i-1][1];
        }

//        assert(k == 69873);
        bool firstBit = _vec[0];

        for(int i=1, p=0; i<k; i+=44, p+=63){
            for(int j=0; j<44; j++) if(_vec[i+j]) decode[i] += (1LL<<j);
            int prv = 0;
            for(int j=0; j<63; j++){
                if(prv == 1){
                    prv = 0;
                    continue;
                }
                if(decode[i] >= DP[63-j][0]){
                    decode[i] -= DP[63-j][0];
                    prv = bits[p+j] = 1;
                }
            }
        }
        if(firstBit){
            for(int i=0; i<n; i++){
                if(bits[i]){
                    bits[i+1] = 1;
                    break;
                }
            }
        }

        int firstZero = -1;
        for(int i=0; i<n; i++){
            if(bits[i]){
                firstZero = i;
                break;
            }
        }
        for(int i=0; i<firstZero; i++) Remove(i);

        bits[n-1] = 1;
        for(int i=firstZero+1; i<n; i++){
            int j = i;
            while(!bits[j]) j++;
            for(int x=j-1; x>=i; x--) remove(x);
            remove(j);
            i=j;
        }
        remove(firstZero);
    }
}

void Bruno(int N, int L, vector<int> A){
    nBruno::Bruno(N, L, A);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 524 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 1 ms 524 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 0 ms 640 KB Output is correct
6 Correct 1 ms 516 KB Output is correct
7 Correct 1 ms 520 KB Output is correct
8 Correct 0 ms 516 KB Output is correct
9 Correct 1 ms 524 KB Output is correct
10 Correct 1 ms 516 KB Output is correct
11 Correct 0 ms 524 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 9412 KB Output is correct
2 Correct 52 ms 9420 KB Output is correct
3 Correct 46 ms 9464 KB Output is correct
4 Correct 49 ms 9500 KB Output is correct
5 Correct 48 ms 9440 KB Output is correct
6 Correct 46 ms 9500 KB Output is correct
7 Correct 48 ms 9400 KB Output is correct
8 Correct 48 ms 9536 KB Output is correct
9 Correct 47 ms 9496 KB Output is correct
10 Correct 47 ms 9496 KB Output is correct
11 Correct 46 ms 9516 KB Output is correct
12 Correct 48 ms 9568 KB Output is correct
13 Correct 54 ms 8940 KB Output is correct
14 Correct 54 ms 9460 KB Output is correct
15 Correct 50 ms 9484 KB Output is correct
16 Correct 51 ms 9512 KB Output is correct
17 Correct 55 ms 8676 KB Output is correct
18 Correct 46 ms 7236 KB Output is correct
19 Correct 44 ms 7268 KB Output is correct
20 Correct 46 ms 9480 KB Output is correct
21 Correct 48 ms 9468 KB Output is correct
22 Correct 54 ms 8712 KB Output is correct
23 Correct 48 ms 9492 KB Output is correct
24 Correct 46 ms 9384 KB Output is correct
25 Correct 44 ms 7220 KB Output is correct
26 Correct 56 ms 8712 KB Output is correct
27 Correct 45 ms 7240 KB Output is correct
28 Correct 53 ms 8724 KB Output is correct
29 Correct 43 ms 7208 KB Output is correct
30 Correct 43 ms 7252 KB Output is correct
31 Correct 43 ms 7272 KB Output is correct
32 Correct 47 ms 9388 KB Output is correct
33 Correct 47 ms 9408 KB Output is correct