oj.uz

Submission #21580

# Submission time Handle Problem Language Result Execution time Memory
21580 2017-04-14T09:56:35 Z Ushio Broken Device (JOI17_broken_device) C++14
85 / 100
 75 ms 4644 KB 
#include "Annalib.h"
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;

namespace {
    const int SZ = 4;
    const int FCT[] = {2, 2, 2, 3};

    int bitCount(int64_t x) {
        int ret = 0;
        while (x) {
            ++ret;
            x &= x - 1;
        }
        return ret;
    }
};

void Anna( int N, long long X, int K, int P[] ){
    vector<int> per(N + FCT[SZ - 1]);
    srand(100);
    for (int i = 0; i < N + FCT[SZ - 1]; ++i) {
        per[i] = i;
    }
    for (int i = 0; i < N; ++i) {
        int pos = i + rand() % (N - i);
        swap(per[i], per[pos]);
    }
    int bit = 0;
    int validity = 0;
    vector<bool> bad(N + FCT[SZ - 1], false);
    for (int i = 0; i < FCT[SZ - 1]; ++i) {
        bad[per[N + i]] = true;
    }
    for (int i = 0; i < K; ++i) {
        bad[P[i]] = true;
    }
    int op = bitCount(X) > 30;
    bool modeSet = false;
    int step = 0;
    for (int i = 0; i < N; ++i) {
        if (validity == 0) {
            if (modeSet) {
                bool ok = bad[per[i]];
                for (int j = 1; j <= FCT[step]; ++j) {
                    ok |= bad[per[i + j]] && bit + j - 1 <= 59 && 
                        ((X & (1LL << (bit + j - 1))) > 0) != op;
                }
                if (ok) {
                    Set(per[i], 0);
                    validity = 0;
                } else {
                    Set(per[i], 1);
                    validity = FCT[step];
                    step = (step + 1) % SZ;
                }
            } else {
                if (bad[per[i]] || (bad[per[i + 1]] && op == 1)) {
                    Set(per[i], 0);
                    validity = 0;
                } else {
                    Set(per[i], 1);
                    validity = 1;
                }
            }
        } else {
            if (modeSet) {
                if (bit <= 59) {
                    if (X & (1LL << bit)) {
                        Set(per[i], 1 ^ op);
                    } else {
                        Set(per[i], op);
                    }
                    bit++;
                } else {
                    Set(per[i], op);
                }
                validity--;
            } else {
                Set(per[i], op);
                modeSet = true;
                validity = 0;
            }
        }
    }
    cerr << "In:  " << X << endl;
}

#include "Brunolib.h"
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;

namespace {
    const int SZ = 4;
    const int FCT[] = {2, 2, 2, 3};
};

long long Bruno( int N, int A[] ){
    vector<int> per(N + FCT[1]);
    srand(100);
    for (int i = 0; i < N + FCT[1]; ++i) {
        per[i] = i;
    }
    for (int i = 0; i < N; ++i) {
        int pos = i + rand() % (N - i);
        swap(per[i], per[pos]);
    }
    int validity = 0;
    int bit = 0;
    int64_t ans = 0;
    bool modeSet = false;
    int op;
    int step = 0;
    for (int i = 0; i < N; ++i) {
        if (validity == 0) {
            if (modeSet) {
                if (A[per[i]]) {
                    validity = FCT[step];
                    step = (step + 1) % SZ;
                } else {
                    validity = 0;
                }
            } else {
                validity = A[per[i]];
            }
        } else {
            if (modeSet) {
                if (bit <= 59) {
                    ans |= ((int64_t) A[per[i]] ^ op) << bit;
                    ++bit;
                }
                validity--;
            } else {
                op = A[per[i]];
                modeSet = true;
                validity = 0;
            }
        }
    }
    cerr << "Out: " << ans << endl;
    return ans;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 58 ms 4644 KB Output is partially correct - L* = 39
2 Partially correct 56 ms 4644 KB Output is partially correct - L* = 39
3 Partially correct 56 ms 4644 KB Output is partially correct - L* = 38
4 Partially correct 62 ms 4644 KB Output is partially correct - L* = 39
5 Correct 48 ms 4644 KB Output is correct - L* = 40
6 Correct 56 ms 4644 KB Output is correct - L* = 40
7 Partially correct 41 ms 4644 KB Output is partially correct - L* = 39
8 Correct 52 ms 4644 KB Output is correct - L* = 40
9 Partially correct 39 ms 4644 KB Output is partially correct - L* = 39
10 Correct 41 ms 4644 KB Output is correct - L* = 40
11 Correct 48 ms 4644 KB Output is correct - L* = 40
12 Partially correct 52 ms 4644 KB Output is partially correct - L* = 39
13 Correct 75 ms 4644 KB Output is correct - L* = 40
14 Correct 27 ms 4644 KB Output is correct - L* = 40
15 Partially correct 52 ms 4644 KB Output is partially correct - L* = 39
16 Partially correct 57 ms 4644 KB Output is partially correct - L* = 39
17 Correct 59 ms 4644 KB Output is correct - L* = 40
18 Correct 62 ms 4644 KB Output is correct - L* = 40
19 Partially correct 45 ms 4644 KB Output is partially correct - L* = 38
20 Correct 46 ms 4644 KB Output is correct - L* = 40
21 Partially correct 45 ms 4644 KB Output is partially correct - L* = 38
22 Correct 62 ms 4644 KB Output is correct - L* = 40
23 Correct 59 ms 4644 KB Output is correct - L* = 40
24 Correct 45 ms 4644 KB Output is correct - L* = 40
25 Correct 52 ms 4644 KB Output is correct - L* = 40
26 Correct 59 ms 4644 KB Output is correct - L* = 40
27 Correct 72 ms 4644 KB Output is correct - L* = 40
28 Correct 52 ms 4644 KB Output is correct - L* = 40
29 Correct 49 ms 4644 KB Output is correct - L* = 40
30 Partially correct 55 ms 4644 KB Output is partially correct - L* = 37
31 Correct 59 ms 4644 KB Output is correct - L* = 40
32 Correct 62 ms 4644 KB Output is correct - L* = 40
33 Partially correct 52 ms 4644 KB Output is partially correct - L* = 38
34 Correct 45 ms 4644 KB Output is correct - L* = 40
35 Partially correct 55 ms 4644 KB Output is partially correct - L* = 38
36 Partially correct 55 ms 4644 KB Output is partially correct - L* = 37
37 Correct 55 ms 4644 KB Output is correct - L* = 40
38 Partially correct 55 ms 4644 KB Output is partially correct - L* = 38
39 Correct 52 ms 4644 KB Output is correct - L* = 40
40 Correct 46 ms 4644 KB Output is correct - L* = 40