oj.uz

Submission #100065

# Submission time Handle Problem Language Result Execution time Memory
100065 2019-03-09T07:59:15 Z jeff Broken Device (JOI17_broken_device) C++14
57 / 100
 76 ms 3152 KB 
#include <bits/stdc++.h>
#include "Annalib.h"
using namespace std;

long long rng(long long i) {
    long long r = 0;
    for (int j = 0; j < 5; ++j) r *= RAND_MAX, r += rand(), r %= i;
    return r;
}

void Anna(int N, long long X, int K, int P[]) {
  	srand(10);
  	X ^= rng(1 << 60);
    int A[50], s[150], i, j, k;
    bool f[N];
    queue<int> q;
    memset(A, -1, sizeof(A));
    for (i = 0; i < N; ++i) f[i] = 1;
    for (i = 0; i < K; ++i) f[P[i]] = 0;
    for (i = 0; i < 150; ++i) s[i] = X % 2, X /= 2, q.push(i);
    j = q.front();
    q.pop();
    k = q.front();
    q.pop();
    for (i = 0; i < N; i += 3) {
        if (j > k) swap(j, k);
        if (!s[j] && !s[k] && f[i] && f[i + 1]) {A[i / 3] = 110; j = q.front(); q.pop(); k = q.front(); q.pop(); continue;}
        if (!s[j] && s[k] && f[i]) {A[i / 3] = 100; j = q.front(); q.pop(); k = q.front(); q.pop(); continue;}
        if (s[j] && s[k] && f[i] && f[i + 2]) {A[i / 3] = 101; j = q.front(); q.pop(); k = q.front(); q.pop(); continue;}
        if (s[j] && !s[k] && f[i] && f[i + 1] && f[i + 2]) {A[i / 3] = 111; j = q.front(); q.pop(); k = q.front(); q.pop(); continue;}
        if (!s[j] && f[i + 1] && f[i + 2]) {A[i / 3] = 11; j = q.front(); q.pop(); continue;}
        if (s[j] && f[i + 1]) {A[i / 3] = 10; j = q.front(); q.pop(); continue;}
        if (!s[k] && f[i + 2]) {A[i / 3] = 1; k = q.front(); q.pop(); continue;}
        A[i / 3] = 0;
    }
    for (i = 0; i < N / 3; ++i) Set(i * 3, A[i] / 100), Set(i * 3 + 1, A[i] / 10 % 10), Set(i * 3 + 2, A[i] % 10);
}
#include <bits/stdc++.h>
#include "Brunolib.h"
using namespace std;

long long rng(long long i) {
    long long r = 0;
    for (int j = 0; j < 5; ++j) r *= RAND_MAX, r += rand(), r %= i;
    return r;
}

long long Bruno(int N, int A[]) {
  	srand(10);
    long long r = 0, l = 1;
    int s[150], i, j, k;
    memset(s, 0, sizeof(s));
    queue<int> q;
    for (i = 0; i < 150; ++i) q.push(i);
    j = q.front();
    q.pop();
    k = q.front();
    q.pop();
    for (i = 0; i < N; i += 3) {
        if (j > k) swap(j, k);
        if (A[i] && A[i + 1] && A[i + 2]) {s[j] = 1; s[k] = 0; j = q.front(); q.pop(); k = q.front(); q.pop(); continue;}
        if (A[i] && A[i + 1]) {s[j] = 0; s[k] = 0; j = q.front(); q.pop(); k = q.front(); q.pop(); continue;}
        if (A[i] && A[i + 2]) {s[j] = 1; s[k] = 1; j = q.front(); q.pop(); k = q.front(); q.pop(); continue;}
        if (A[i + 1] && A[i + 2]) {s[j] = 0; j = q.front(); q.pop(); continue;}
        if (A[i]) {s[j] = 0; s[k] = 1; j = q.front(); q.pop(); k = q.front(); q.pop(); continue;}
        if (A[i + 1]) {s[j] = 1; j = q.front(); q.pop(); continue;}
        if (A[i + 2]) {s[k] = 0; k = q.front(); q.pop(); continue;}
    }
    for (i = 0; i < 150 && s[i] > -1; ++i) {
        r += l * s[i];
        l *= 2;
    }
  	r ^= rng(1 << 60);
    return r;
}

Compilation message

Anna.cpp: In function 'void Anna(int, long long int, int, int*)':
Anna.cpp:13:18: warning: left shift count >= width of type [-Wshift-count-overflow]
    X ^= rng(1 << 60);
                  ^~

Bruno.cpp: In function 'long long int Bruno(int, int*)':
Bruno.cpp:36:18: warning: left shift count >= width of type [-Wshift-count-overflow]
    r ^= rng(1 << 60);
                  ^~

Subtask #1
57.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 3056 KB Output is correct - L* = 40
2 Correct 57 ms 3056 KB Output is correct - L* = 40
3 Correct 39 ms 3072 KB Output is correct - L* = 40
4 Correct 39 ms 3072 KB Output is correct - L* = 40
5 Correct 47 ms 3056 KB Output is correct - L* = 40
6 Correct 54 ms 3056 KB Output is correct - L* = 40
7 Correct 76 ms 3056 KB Output is correct - L* = 40
8 Correct 48 ms 2920 KB Output is correct - L* = 40
9 Correct 41 ms 3088 KB Output is correct - L* = 40
10 Correct 48 ms 2968 KB Output is correct - L* = 40
11 Correct 47 ms 2888 KB Output is correct - L* = 40
12 Correct 60 ms 3056 KB Output is correct - L* = 40
13 Correct 51 ms 3016 KB Output is correct - L* = 40
14 Partially correct 54 ms 3072 KB Output is partially correct - L* = 39
15 Correct 64 ms 3072 KB Output is correct - L* = 40
16 Correct 48 ms 3072 KB Output is correct - L* = 40
17 Partially correct 42 ms 3072 KB Output is partially correct - L* = 39
18 Correct 45 ms 2816 KB Output is correct - L* = 40
19 Partially correct 56 ms 3072 KB Output is partially correct - L* = 23
20 Correct 46 ms 2920 KB Output is correct - L* = 40
21 Correct 41 ms 3072 KB Output is correct - L* = 40
22 Correct 39 ms 3072 KB Output is correct - L* = 40
23 Correct 53 ms 3152 KB Output is correct - L* = 40
24 Partially correct 55 ms 3064 KB Output is partially correct - L* = 32
25 Correct 48 ms 3056 KB Output is correct - L* = 40
26 Correct 62 ms 3000 KB Output is correct - L* = 40
27 Correct 56 ms 3056 KB Output is correct - L* = 40
28 Partially correct 47 ms 3072 KB Output is partially correct - L* = 39
29 Correct 46 ms 3072 KB Output is correct - L* = 40
30 Correct 51 ms 3072 KB Output is correct - L* = 40
31 Correct 42 ms 3072 KB Output is correct - L* = 40
32 Correct 56 ms 2960 KB Output is correct - L* = 40
33 Correct 47 ms 3056 KB Output is correct - L* = 40
34 Correct 45 ms 3080 KB Output is correct - L* = 40
35 Partially correct 53 ms 3008 KB Output is partially correct - L* = 37
36 Correct 51 ms 3072 KB Output is correct - L* = 40
37 Correct 46 ms 3016 KB Output is correct - L* = 40
38 Correct 55 ms 3056 KB Output is correct - L* = 40
39 Correct 55 ms 3072 KB Output is correct - L* = 40
40 Correct 53 ms 2968 KB Output is correct - L* = 40