oj.uz

Submission #426646

# Submission time Handle Problem Language Result Execution time Memory
426646 2021-06-14T08:34:12 Z 반딧불(#7615) Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 71 ms 7556 KB 
#include "Anna.h"
#include <bits/stdc++.h>

using namespace std;

typedef __int128 ll;

namespace {
    int n;
    bool arr[100002];
    ll DP[502][2];
    ll power[102];
}

void doSmall(vector<char> &S){
    int xOpen = -1;
    for(int i=0; i<n; i++){
        if(xOpen == -1){
            if(S[i] != 'X') Send(0);
            else{
                Send(1);
                xOpen = i;
            }
            continue;
        }

        if(S[i] == 'Z' && S[i+1] != 'Z') Send(1);
        else Send(0);
    }
}

void Anna(int N, vector<char> S) {
    n = N;
    if(n<=70000){
        doSmall(S);
        return;
    }

    power[0] = 1;
    for(int i=1; i<=100; i++){
        power[i] = power[i-1] * 2;
    }

    int xOpen = -1;
    int strange = 0;
    for(int i=0; i<n; i++){
        if(xOpen == -1){
            if(S[i] != 'X'){}
            else{
                arr[i] = 1;
                xOpen = i;
            }
            continue;
        }

        if(S[i] == 'Z' && S[i+1] != 'Z'){
            if(arr[i-1] == 1) strange = i;
            else arr[i] = 1;
        }
    }

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

    for(int d=0; d<1000; d++){
        int L = d*100, R = L+100;
        int cnt = accumulate(arr+L, arr+R, 0);
        ll sum = 0;

        for(int i=100, x=L; x<R; x++, i--){
            if(arr[x]){
                sum += DP[i][0];
            }
        }
        for(ll i=0; i<69; i++){
            Send((sum>>i)&1);
        }
    }

    for(int d=0; d<20; d++) Send((strange>>d)&1);
}

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

using namespace std;

typedef __int128 ll;

namespace {
    int n;
    int arr[100002];
    ll DP[502][2];
    ll power[102];
    vector<int> X, Z;
}  // namespace

void Bruno(int N, int L, vector<int> A) {
    n = N;
    if(n<=70000){
        for(int i=0; i<n; i++){
            arr[i] = A[i];
        }
    }
    else{
        DP[0][0] = 1;
        for(int i=1; i<=100; i++){
            DP[i][0] = DP[i-1][0] + DP[i-1][1];
            DP[i][1] = DP[i-1][0];
        }

        power[0] = 1;
        for(int i=1; i<=100; i++){
            power[i] = power[i-1] * 2;
        }

        for(int d=0; d<1000; d++){
            int L = d*100, R = d*100;
            ll sum = 0;
            for(ll x=0; x<69; x++){
                if(A[d*69+x]) sum += power[x];
            }
            for(int i=100, x=L; x<R; i--, x++){
                if(sum >= DP[i][0]){
                    arr[x] = 1;
                    sum -= DP[i][0];
                }
            }
        }

        ll tmp = 0;
        for(ll x=0; x<20; x++){
            if(A[1000*69+x]) tmp += (1<<x);
        }
        if(tmp) arr[tmp] = 1;
    }


    int f = -1;
    for(int i=0; i<n; i++){
        if(f == -1){
            if(!arr[i]) Remove(i);
            else f=i;
            continue;
        }
        if(arr[i]){
            Remove(i);
            continue;
        }
        int j = i;
        while(j+1<n && !arr[j+1]) j++;
        for(int k=j; k>=i; k--) Remove(k);
        i=j;
    }

    if(f != -1) Remove(f);
}

Compilation message

Anna.cpp: In function 'void Anna(int, std::vector<char>)':
Anna.cpp:70:13: warning: unused variable 'cnt' [-Wunused-variable]
   70 |         int cnt = accumulate(arr+L, arr+R, 0);
      |             ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 484 KB Output is correct
2 Correct 1 ms 484 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 480 KB Output is correct
6 Correct 1 ms 484 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 1 ms 488 KB Output is correct
9 Correct 0 ms 484 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 1 ms 480 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 7556 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -