답안 #565323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565323	2022-05-20T17:05:28 Z	Sorting	Broken Device 2 (JOI22_device2)	C++17	80 / 100	119 ms	3548 KB

Anna
Bruno

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

using namespace std;

typedef long long ll;

static const int BITS = 60;
static const int C = 3;

static const int LEN = 178;

static mt19937 mt(1432);

int Declare() {
    return LEN;
}

static vector<int> gen_seq(){
    vector<int> v(BITS);
    for(int i = 0; i < BITS; ++i)
        v[i] = uniform_int_distribution<int>(0, 1)(mt);
    return v;
}

pair<vector<int>, vector<int>> Anna(ll a) {
    vector<int> rand_seq = gen_seq();

    vector<int> v1, v2;
    for(ll i = 0; i < LEN; i += 2){
        v1.push_back(0);
        v1.push_back(1);
    }
    vector<int> seq;
    for(ll i = 0; i < BITS; ++i){
        ll bit = (a >> i) & 1ll;
        seq.push_back(bit);
    }

    for(int i = 0; i < BITS; ++i)
        seq[i] ^= rand_seq[i];

    ll cnt = 1;
    for(ll i = 1; i <= BITS; ++i){
        if(i == BITS || seq[i] != seq[i - 1]){
            for(ll j = 0; j < 2 * cnt + 1; ++j)
                v2.push_back(seq[i - 1]);
            cnt = 0;
        }
        ++cnt;
    }

    while(v2.size() < LEN)
        v2.push_back(0);

    assert((int)v2.size() == LEN);

    return {v1, v2};
}

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

using namespace std;

typedef long long ll;

static const int BITS = 60;
static const int C = 3;

static mt19937 mt(1432);

static vector<int> gen_seq(){
    vector<int> v(BITS);
    for(int i = 0; i < BITS; ++i)
        v[i] = uniform_int_distribution<int>(0, 1)(mt);
    return v;
}


ll Bruno(vector<int> u) {
    vector<int> rand_seq = gen_seq();

    ll curr = 0, prefix = 0, dir = 0;
    vector<ll> bits;
    for(ll i = 0; i < u.size(); ++i){
        prefix += u[i] ? 1 : -1;

        if(dir == -1 && prefix <= curr - (C - 1)){
            bits.push_back(0);
            curr -= C - 1;
            continue;
        }
        if(dir == 1 && prefix >= curr + C - 2){
            bits.push_back(1);
            curr += C - 1;
            continue;
        }

        if(prefix <= curr - C){
            bits.push_back(0);
            curr -= C;
            dir = -1;
        }
        else if(prefix >= curr + C - 1){
            bits.push_back(1);
            curr += C;
            dir = 1;
        }
    }

    ll ans = 0;
    assert(bits.size() >= BITS);
    bits.resize(BITS);
    for(int i = 0; i < BITS; ++i)
        bits[i] ^= rand_seq[i];

    for(ll i = 0; i < bits.size(); ++i)
        ans += bits[i] << i;
    return ans;
}

Compilation message

Bruno.cpp: In function 'll Bruno(std::vector<int>)':
Bruno.cpp:26:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(ll i = 0; i < u.size(); ++i){
      |                   ~~^~~~~~~~~~
Bruno.cpp:58:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(ll i = 0; i < bits.size(); ++i)
      |                   ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	516 KB	Output is correct
2	Correct	83 ms	3504 KB	Output is correct
3	Correct	85 ms	3392 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	516 KB	Output is correct
2	Correct	83 ms	3504 KB	Output is correct
3	Correct	85 ms	3392 KB	Output is correct
4	Correct	99 ms	3412 KB	Output is correct
5	Correct	85 ms	3412 KB	Output is correct
6	Correct	83 ms	3496 KB	Output is correct
7	Correct	99 ms	3520 KB	Output is correct
8	Correct	94 ms	3344 KB	Output is correct
9	Correct	88 ms	3300 KB	Output is correct
10	Correct	94 ms	3364 KB	Output is correct

Subtask #3
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	516 KB	Output is correct
2	Correct	83 ms	3504 KB	Output is correct
3	Correct	85 ms	3392 KB	Output is correct
4	Correct	99 ms	3412 KB	Output is correct
5	Correct	85 ms	3412 KB	Output is correct
6	Correct	83 ms	3496 KB	Output is correct
7	Correct	99 ms	3520 KB	Output is correct
8	Correct	94 ms	3344 KB	Output is correct
9	Correct	88 ms	3300 KB	Output is correct
10	Correct	94 ms	3364 KB	Output is correct
11	Correct	99 ms	3332 KB	Output is correct
12	Correct	84 ms	3432 KB	Output is correct
13	Correct	86 ms	3404 KB	Output is correct
14	Correct	86 ms	3316 KB	Output is correct
15	Correct	91 ms	3476 KB	Output is correct
16	Correct	114 ms	3468 KB	Output is correct
17	Correct	86 ms	3296 KB	Output is correct
18	Correct	86 ms	3476 KB	Output is correct
19	Correct	90 ms	3388 KB	Output is correct
20	Correct	86 ms	3428 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	516 KB	Output is correct
2	Correct	83 ms	3504 KB	Output is correct
3	Correct	85 ms	3392 KB	Output is correct
4	Correct	99 ms	3412 KB	Output is correct
5	Correct	85 ms	3412 KB	Output is correct
6	Correct	83 ms	3496 KB	Output is correct
7	Correct	99 ms	3520 KB	Output is correct
8	Correct	94 ms	3344 KB	Output is correct
9	Correct	88 ms	3300 KB	Output is correct
10	Correct	94 ms	3364 KB	Output is correct
11	Correct	99 ms	3332 KB	Output is correct
12	Correct	84 ms	3432 KB	Output is correct
13	Correct	86 ms	3404 KB	Output is correct
14	Correct	86 ms	3316 KB	Output is correct
15	Correct	91 ms	3476 KB	Output is correct
16	Correct	114 ms	3468 KB	Output is correct
17	Correct	86 ms	3296 KB	Output is correct
18	Correct	86 ms	3476 KB	Output is correct
19	Correct	90 ms	3388 KB	Output is correct
20	Correct	86 ms	3428 KB	Output is correct
21	Correct	113 ms	3428 KB	Output is correct
22	Correct	99 ms	3548 KB	Output is correct
23	Correct	104 ms	3516 KB	Output is correct
24	Correct	94 ms	3432 KB	Output is correct
25	Correct	112 ms	3484 KB	Output is correct
26	Correct	101 ms	3480 KB	Output is correct
27	Correct	86 ms	3472 KB	Output is correct
28	Correct	92 ms	3460 KB	Output is correct
29	Correct	90 ms	3492 KB	Output is correct
30	Correct	96 ms	3384 KB	Output is correct

Subtask #5
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	516 KB	Output is correct
2	Correct	83 ms	3504 KB	Output is correct
3	Correct	85 ms	3392 KB	Output is correct
4	Correct	99 ms	3412 KB	Output is correct
5	Correct	85 ms	3412 KB	Output is correct
6	Correct	83 ms	3496 KB	Output is correct
7	Correct	99 ms	3520 KB	Output is correct
8	Correct	94 ms	3344 KB	Output is correct
9	Correct	88 ms	3300 KB	Output is correct
10	Correct	94 ms	3364 KB	Output is correct
11	Correct	99 ms	3332 KB	Output is correct
12	Correct	84 ms	3432 KB	Output is correct
13	Correct	86 ms	3404 KB	Output is correct
14	Correct	86 ms	3316 KB	Output is correct
15	Correct	91 ms	3476 KB	Output is correct
16	Correct	114 ms	3468 KB	Output is correct
17	Correct	86 ms	3296 KB	Output is correct
18	Correct	86 ms	3476 KB	Output is correct
19	Correct	90 ms	3388 KB	Output is correct
20	Correct	86 ms	3428 KB	Output is correct
21	Correct	113 ms	3428 KB	Output is correct
22	Correct	99 ms	3548 KB	Output is correct
23	Correct	104 ms	3516 KB	Output is correct
24	Correct	94 ms	3432 KB	Output is correct
25	Correct	112 ms	3484 KB	Output is correct
26	Correct	101 ms	3480 KB	Output is correct
27	Correct	86 ms	3472 KB	Output is correct
28	Correct	92 ms	3460 KB	Output is correct
29	Correct	90 ms	3492 KB	Output is correct
30	Correct	96 ms	3384 KB	Output is correct
31	Correct	115 ms	3432 KB	Output is correct
32	Correct	92 ms	3424 KB	Output is correct
33	Correct	96 ms	3328 KB	Output is correct
34	Correct	99 ms	3480 KB	Output is correct
35	Correct	101 ms	3452 KB	Output is correct
36	Correct	98 ms	3384 KB	Output is correct
37	Correct	96 ms	3528 KB	Output is correct
38	Correct	99 ms	3392 KB	Output is correct
39	Correct	106 ms	3416 KB	Output is correct
40	Correct	104 ms	3508 KB	Output is correct

Subtask #6
40.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	91 ms	3452 KB	Output is partially correct
2	Partially correct	94 ms	3532 KB	Output is partially correct
3	Partially correct	119 ms	3488 KB	Output is partially correct
4	Partially correct	103 ms	3476 KB	Output is partially correct
5	Partially correct	91 ms	3396 KB	Output is partially correct
6	Partially correct	105 ms	3488 KB	Output is partially correct
7	Partially correct	117 ms	3420 KB	Output is partially correct
8	Partially correct	90 ms	3468 KB	Output is partially correct
9	Partially correct	90 ms	3384 KB	Output is partially correct
10	Partially correct	88 ms	3516 KB	Output is partially correct
11	Partially correct	95 ms	3480 KB	Output is partially correct
12	Partially correct	92 ms	3452 KB	Output is partially correct
13	Partially correct	118 ms	3512 KB	Output is partially correct
14	Partially correct	87 ms	3384 KB	Output is partially correct
15	Partially correct	95 ms	3388 KB	Output is partially correct
16	Partially correct	101 ms	3296 KB	Output is partially correct
17	Partially correct	89 ms	3540 KB	Output is partially correct
18	Partially correct	86 ms	3328 KB	Output is partially correct
19	Partially correct	83 ms	3500 KB	Output is partially correct
20	Partially correct	88 ms	3452 KB	Output is partially correct

답안 #565323

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 3.0 / 3.0

Subtask #4 12.0 / 12.0

Subtask #5 15.0 / 15.0

Subtask #6 40.0 / 60.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
3.0 / 3.0

Subtask #4
12.0 / 12.0

Subtask #5
15.0 / 15.0

Subtask #6
40.0 / 60.0