oj.uz

답안 #426672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
426672 2021-06-14T08:54:20 Z 반딧불(#7615) Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 89 ms 7988 KB 
#include "Anna.h"
#include <bits/stdc++.h>

#ifdef TEST
#define LIM_A 50
#define LIM_B 35
typedef long long ll;
#else
#define LIM_A 100
#define LIM_B 70
typedef __int128 ll;
#endif // TEST

using namespace std;

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) {
    int LIM = (N + LIM_A - 1) / LIM_A;
    LIM = 100000 / LIM_A;
    n = N;
//    if(n<=70000){
//        doSmall(S);
//        return;
//    }

    power[0] = 1;
    for(int i=1; i<=LIM_A; 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<=LIM_A; i++){
        DP[i][0] = DP[i-1][0] + DP[i-1][1];
        DP[i][1] = DP[i-1][0];
    }

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

        for(int i=LIM_A, x=L; x<R; x++, i--){
            if(arr[x]){
                sum += DP[i][0];
            }
        }
        for(int i=0; i<LIM_B; i++){
            ll tmp = sum;
            for(int a=0; a<i; a++) tmp /= ll(2);
            Send(tmp%2);
        }
    }
    Send(strange);
}

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

#ifdef TEST
#define LIM_A 50
#define LIM_B 35
typedef long long ll;
#else
#define LIM_A 100
#define LIM_B 70
typedef __int128 ll;
#endif // TEST

using namespace std;

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;
    int LIM = (N + LIM_A - 1) / LIM_A;
    LIM = 100000 / LIM_A;
//    if(n<=70000){
//        for(int i=0; i<n; i++){
//            arr[i] = A[i];
//        }
//    }
    DP[0][0] = 1;
    for(int i=1; i<=LIM_A; 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<=LIM_A; i++){
        power[i] = power[i-1] * 2;
    }

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

    if(A.back()){
        for(int i=0; i<n; i++){
            if(arr[i]) arr[i+1] = 1;
            break;
        }
    }


    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:80:13: warning: unused variable 'cnt' [-Wunused-variable]
   80 |         int cnt = accumulate(arr+L, arr+R, 0);
      |             ^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1912 KB Output is correct
2 Correct 20 ms 1892 KB Output is correct
3 Correct 22 ms 1888 KB Output is correct
4 Correct 22 ms 1872 KB Output is correct
5 Correct 28 ms 1832 KB Output is correct
6 Correct 25 ms 1852 KB Output is correct
7 Correct 23 ms 1900 KB Output is correct
8 Correct 30 ms 1892 KB Output is correct
9 Correct 20 ms 1912 KB Output is correct
10 Correct 20 ms 1880 KB Output is correct
11 Correct 23 ms 1892 KB Output is correct

Subtask #2
0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 86 ms 7868 KB Partially correct
2 Partially correct 89 ms 7864 KB Partially correct
3 Partially correct 68 ms 7956 KB Partially correct
4 Partially correct 67 ms 7940 KB Partially correct
5 Partially correct 69 ms 7904 KB Partially correct
6 Partially correct 66 ms 7988 KB Partially correct
7 Partially correct 67 ms 7956 KB Partially correct
8 Partially correct 78 ms 7892 KB Partially correct
9 Partially correct 72 ms 7940 KB Partially correct
10 Partially correct 76 ms 7916 KB Partially correct
11 Partially correct 69 ms 7944 KB Partially correct
12 Incorrect 13 ms 1504 KB Wrong Answer [1]
13 Halted 0 ms 0 KB -