oj.uz

Submission #991510

# Submission time Handle Problem Language Result Execution time Memory
991510 2024-06-02T10:54:23 Z Sharky Broken Device (JOI17_broken_device) C++17
0 / 100
 33 ms 2660 KB 
#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;

namespace anna {
const long long purple = 694202512019219198LL;
const int amogus = 696969;

mt19937 rng(amogus);
vector<int> p(151), inv(151);

int rnd(int u, int v) {
    return uniform_int_distribution<int> (u, v) (rng);
}

void gen_perm() {
    for (int i = 0; i < 150; i++) p[i] = i;
    for (int i = 0; i < 150; i++) swap(p[rnd(0, 149)], p[rnd(0, 149)]);
    for (int i = 0; i < 150; i++) inv[p[i]] = i;
}
}

using namespace anna;

// p = 3 1 2 4 0
// inv[3] = 0;
// inv[1] = 1;
// inv[2] = 2;
// inv[4] = 3;
// inv[0] = 4;

// inv = {4, 1, 2, 0, 3};

// say P = {4}
// new P = {0}

// 0: 1
// 1: 2
// 01: 3
// 11: 4

void Anna(int N, long long _X, int K, int P[]){
    long long X = _X;
    gen_perm();
    X ^= purple;
    vector<int> bit, seq(N, 0), li;
    for (int i = 59; i >= 0; i--) bit.push_back((X & (1LL << i)) ? 1 : 0);
    li.push_back(-1);
    vector<int> pp(K, 0);
    for (int i = 0; i < K; i++) {
        pp[i] = p[P[i]];
        li.push_back(pp[i]);
    };
    li.push_back(N);
    sort(li.begin(), li.end());
    int cur = 0;
    int ptr = 0;
    for (int i = 1; i < li.size(); i++) {
        int l = li[i - 1] + 1, r = li[i] - 1;
        // cout << l << ' ' << r << '\n';
        ptr = l;
        int dist = r - l + 1;
        while (true) {
            if (cur < 59 && bit[cur] == 1 && bit[cur + 1] == 1 && dist >= 4) {
                dist -= 4;
                cur += 2;
                seq[ptr] = seq[ptr + 1] = seq[ptr + 2] = seq[ptr + 3] = 1;
                ptr += 4;
            } else if (cur < 59 && bit[cur] == 0 && bit[cur + 1] == 1 && dist >= 3) {
                dist -= 3;
                cur += 2;
                seq[ptr] = seq[ptr + 1] = seq[ptr + 2] = 1;
                ptr += 3;
            } else if (cur < 60 && bit[cur] == 1 && dist >= 2) {
                dist -= 2;
                cur++;
                seq[ptr] = seq[ptr + 1] = 1;
                ptr += 2;
            } else if (cur < 60 && bit[cur] == 0 && dist >= 1) {
                dist -= 1;
                cur++;
                seq[ptr] = 1;
                ptr += 1;
            } else break;
            if (ptr < r) seq[ptr++] = 0, dist--;
        }
        while (ptr <= r) seq[ptr++] = 0;
    }
    // for (int i = 0; i < N; i++) cout << seq[i] << ' ';
    // cout << '\n';
    vector<int> vt;
    for (int i = 0; i < N; i++) {
        // if (seq[i]) cout << inv[i] << ' ';
        Set(inv[i], seq[i]);
    }
    cout << '\n';
}
#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;

namespace bruno {
const long long purple = 694202512019219198LL;
const int amogus = 696969;

mt19937 rng(amogus);
vector<int> p(151), inv(151);

int rnd(int u, int v) {
    return uniform_int_distribution<int> (u, v) (rng);
}

void gen_perm() {
    for (int i = 0; i < 150; i++) p[i] = i;
    for (int i = 0; i < 150; i++) swap(p[rnd(0, 149)], p[rnd(0, 149)]);
    for (int i = 0; i < 150; i++) inv[p[i]] = i;
}
}

using namespace bruno;

// 0: 1
// 1: 2
// 01: 3
// 11: 4

long long Bruno(int N, int A[]) {
    gen_perm();
    vector<int> bits;
    long long X = 0;
    vector<int> a(N), z, g;
    for (int i = 0; i < N; i++) {
        a[i] = A[inv[i]];
        // if (a[i]) cout << inv[i] << ' ';
    }
    // cout << '\n';
    // for (int i = 0; i < N; i++) cout << a[i] << ' ';
    // cout << '\n';
    z.push_back(-1);
    for (int i = 0; i < N; i++) if (!a[i]) z.push_back(i);
    z.push_back(N);
    for (int i = 1; i < z.size(); i++) g.push_back(z[i] - z[i - 1]);
    for (int i = 0; i < g.size(); i++) {
        if (g[i] == 1) {
            bits.push_back(0);
        } else if (g[i] == 2) {
            bits.push_back(1);
        } else if (g[i] == 3) {
            bits.push_back(0);
            bits.push_back(1);
        } else if (g[i] == 4) {
            bits.push_back(1);
            bits.push_back(1);
        }
    }
    for (int i = 0; i < bits.size(); i++) {
        X *= 2;
        X += bits[i];
    }
    X ^= purple;
    return X;
}

Compilation message

Anna.cpp: In function 'void Anna(int, long long int, int, int*)':
Anna.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 1; i < li.size(); i++) {
      |                     ~~^~~~~~~~~~~

Bruno.cpp: In function 'long long int Bruno(int, int*)':
Bruno.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 1; i < z.size(); i++) g.push_back(z[i] - z[i - 1]);
      |                     ~~^~~~~~~~~~
Bruno.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < g.size(); i++) {
      |                     ~~^~~~~~~~~~
Bruno.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < bits.size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2628 KB Program terminated incorrectly, or you printed something to stdout
2 Incorrect 27 ms 2296 KB Program terminated incorrectly, or you printed something to stdout
3 Incorrect 17 ms 2648 KB Program terminated incorrectly, or you printed something to stdout
4 Incorrect 17 ms 2400 KB Program terminated incorrectly, or you printed something to stdout
5 Incorrect 19 ms 2568 KB Program terminated incorrectly, or you printed something to stdout
6 Incorrect 19 ms 2396 KB Program terminated incorrectly, or you printed something to stdout
7 Incorrect 33 ms 2428 KB Program terminated incorrectly, or you printed something to stdout
8 Incorrect 21 ms 2624 KB Program terminated incorrectly, or you printed something to stdout
9 Incorrect 23 ms 2628 KB Program terminated incorrectly, or you printed something to stdout
10 Incorrect 18 ms 2372 KB Program terminated incorrectly, or you printed something to stdout
11 Incorrect 17 ms 2524 KB Program terminated incorrectly, or you printed something to stdout
12 Incorrect 18 ms 2652 KB Program terminated incorrectly, or you printed something to stdout
13 Incorrect 21 ms 2384 KB Program terminated incorrectly, or you printed something to stdout
14 Incorrect 19 ms 2648 KB Program terminated incorrectly, or you printed something to stdout
15 Incorrect 19 ms 2648 KB Program terminated incorrectly, or you printed something to stdout
16 Incorrect 19 ms 2624 KB Program terminated incorrectly, or you printed something to stdout
17 Incorrect 33 ms 2304 KB Program terminated incorrectly, or you printed something to stdout
18 Incorrect 18 ms 2652 KB Program terminated incorrectly, or you printed something to stdout
19 Incorrect 22 ms 2376 KB Program terminated incorrectly, or you printed something to stdout
20 Incorrect 18 ms 2624 KB Program terminated incorrectly, or you printed something to stdout
21 Incorrect 17 ms 2660 KB Program terminated incorrectly, or you printed something to stdout
22 Incorrect 19 ms 2644 KB Program terminated incorrectly, or you printed something to stdout
23 Incorrect 22 ms 2560 KB Program terminated incorrectly, or you printed something to stdout
24 Incorrect 30 ms 2652 KB Program terminated incorrectly, or you printed something to stdout
25 Incorrect 19 ms 2368 KB Program terminated incorrectly, or you printed something to stdout
26 Incorrect 30 ms 2372 KB Program terminated incorrectly, or you printed something to stdout
27 Incorrect 19 ms 2532 KB Program terminated incorrectly, or you printed something to stdout
28 Incorrect 25 ms 2312 KB Program terminated incorrectly, or you printed something to stdout
29 Incorrect 23 ms 2604 KB Program terminated incorrectly, or you printed something to stdout
30 Incorrect 18 ms 2624 KB Program terminated incorrectly, or you printed something to stdout
31 Incorrect 17 ms 2448 KB Program terminated incorrectly, or you printed something to stdout
32 Incorrect 19 ms 2400 KB Program terminated incorrectly, or you printed something to stdout
33 Incorrect 18 ms 2624 KB Program terminated incorrectly, or you printed something to stdout
34 Incorrect 25 ms 2540 KB Program terminated incorrectly, or you printed something to stdout
35 Incorrect 28 ms 2364 KB Program terminated incorrectly, or you printed something to stdout
36 Incorrect 18 ms 2372 KB Program terminated incorrectly, or you printed something to stdout
37 Incorrect 27 ms 2412 KB Program terminated incorrectly, or you printed something to stdout
38 Incorrect 17 ms 2628 KB Program terminated incorrectly, or you printed something to stdout
39 Incorrect 17 ms 2452 KB Program terminated incorrectly, or you printed something to stdout
40 Incorrect 17 ms 2660 KB Program terminated incorrectly, or you printed something to stdout