Submission #21564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
21564	2017-04-14T09:25:53 Z	Ushio	Broken Device (JOI17_broken_device)	C++14	65 / 100	72 ms	4644 KB

Anna

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

const int FCT = 10;

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);
    srand(16);
    for (int i = 0; i < N + FCT; ++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, false);
    for (int i = 0; i < FCT; ++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;
    for (int i = 0; i < N; ++i) {
        if (validity == 0) {
            if (modeSet) {
                bool ok = bad[per[i]];
                for (int j = 1; j <= FCT; ++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;
                }
            } 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;
}

Bruno

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

const int FCT = 10;

long long Bruno( int N, int A[] ){
    vector<int> per(N + 1);
    srand(16);
    for (int i = 0; i < N + 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;
    for (int i = 0; i < N; ++i) {
        if (validity == 0) {
            if (modeSet) {
                validity = A[per[i]] * FCT;
            } 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

65.0 / 100.0

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