oj.uz

Submission #1078494

# Submission time Handle Problem Language Result Execution time Memory
1078494 2024-08-27T18:45:29 Z someone Broken Device (JOI17_broken_device) C++14
0 / 100
 1218 ms 980 KB 
#include "Annalib.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using i64 = long long;
using namespace std;

const i64 MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;

bool backtrack(int i, i64 rem, vector<array<int, 2>>& crt, vector<i64>& sumAft, vector<int>& used) {
    if(i == sz(crt)) return false;
    if(rem > sumAft[i]) return false;
    if(rem == crt[i][0]) {
        used.push_back(crt[i][1]);
        return true;
    }
    if(rem > crt[i][0]) {
        if(backtrack(i+1, rem - crt[i][0], crt, sumAft, used)) {
            used.push_back(crt[i][1]);
            return true;
        }
    }
    return backtrack(i+1, rem, crt, sumAft, used);
}

void Anna(int N, long long X, int K, int P[]) {
    vector<bool> broken(N);
    for(int i = 0; i < K; i++)
        broken[P[i]] = 1;
    
    mt19937 rng(42);
    X ^= rng();
    vector<array<int, 2>> crt[2];
    vector<i64> sumAft[2];
    for(int i = 0; i < N/2; i++) {
        int val = rng() % MOD1;
        if(!broken[i]) crt[0].push_back({val, i});
    }
    for(int i = N/2; i < N; i++) {
        int val = rng() % MOD2;
        if(!broken[i]) crt[1].push_back({val, i});
    }

    sort(all(crt[0])); reverse(all(crt[0]));
    sort(all(crt[1])); reverse(all(crt[1]));
    for(int i = 0; i < 2; i++) {
        sumAft[i].resize(sz(crt[i]));
        for(int j = sz(crt[i])-2; j >= 0; j--)
            sumAft[i][j] = sumAft[i][j+1] + crt[i][j+1][0];
        for(int j = 0; j < sz(crt[i]); j++)
            sumAft[i][j] += crt[i][j][0];
    }
    vector<int> used[2];
    for(int i = 0; i < 76; i++) {
        if(backtrack(0, X % MOD1 + i * MOD1, crt[0], sumAft[0], used[0])) {
            i = 76;
        }
    }
    for(int i = 0; i < 76; i++) {
        if(backtrack(0, X % MOD2 + i * MOD2, crt[1], sumAft[1], used[1])) {
            i = 76;
        }
    }
    for(int i : used[0]) Set(i, 1);
    for(int i : used[1]) Set(i, 1);
}

#include "Brunolib.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using i64 = long long;
using namespace std;

const i64 MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;

using ll = __int128;

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, a;
	ll d = euclid(b, a % b, y, x);
	return y -= a/b * x, d;
}

ll crt(ll a, ll m, ll b, ll n) {
	if (n > m) swap(a, b), swap(m, n);
	ll x, y, g = euclid(m, n, x, y);
	assert((a - b) % g == 0); // else no solution
	x = (b - a) % n * x % n / g * m + a;
	return x < 0 ? x + m*n/g : x;
}

long long Bruno( int N, int A[] ){
    mt19937 rng(42);
    i64 xored = rng(), a = 0, b = 0;
    for(int i = 0; i < N/2; i++) {
        i64 val = rng();
        if(A[i]) a ^= val;
    }
    for(int i = N/2; i < N; i++) {
        i64 val = rng();
        if(A[i]) b ^= val;
    }

    return ((i64)crt(a, MOD1, b, MOD2)) ^ xored;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 732 KB Wrong Answer [4]
2 Incorrect 92 ms 812 KB Wrong Answer [4]
3 Incorrect 86 ms 716 KB Wrong Answer [4]
4 Incorrect 128 ms 812 KB Wrong Answer [4]
5 Incorrect 1218 ms 808 KB Wrong Answer [4]
6 Incorrect 345 ms 840 KB Wrong Answer [4]
7 Incorrect 270 ms 716 KB Wrong Answer [4]
8 Incorrect 72 ms 728 KB Wrong Answer [4]
9 Incorrect 180 ms 716 KB Wrong Answer [4]
10 Incorrect 386 ms 720 KB Wrong Answer [4]
11 Incorrect 148 ms 720 KB Wrong Answer [4]
12 Incorrect 42 ms 808 KB Wrong Answer [4]
13 Incorrect 298 ms 824 KB Wrong Answer [4]
14 Incorrect 547 ms 972 KB Wrong Answer [4]
15 Incorrect 639 ms 720 KB Wrong Answer [4]
16 Incorrect 24 ms 712 KB Wrong Answer [4]
17 Incorrect 70 ms 732 KB Wrong Answer [4]
18 Incorrect 363 ms 716 KB Wrong Answer [4]
19 Incorrect 332 ms 716 KB Wrong Answer [4]
20 Incorrect 214 ms 716 KB Wrong Answer [4]
21 Incorrect 497 ms 980 KB Wrong Answer [4]
22 Incorrect 638 ms 836 KB Wrong Answer [4]
23 Incorrect 704 ms 820 KB Wrong Answer [4]
24 Incorrect 370 ms 712 KB Wrong Answer [4]
25 Incorrect 382 ms 716 KB Wrong Answer [4]
26 Incorrect 278 ms 712 KB Wrong Answer [4]
27 Incorrect 83 ms 964 KB Wrong Answer [4]
28 Incorrect 122 ms 716 KB Wrong Answer [4]
29 Incorrect 232 ms 716 KB Wrong Answer [4]
30 Incorrect 277 ms 816 KB Wrong Answer [4]
31 Incorrect 127 ms 716 KB Wrong Answer [4]
32 Incorrect 145 ms 720 KB Wrong Answer [4]
33 Incorrect 140 ms 820 KB Wrong Answer [4]
34 Incorrect 190 ms 720 KB Wrong Answer [4]
35 Incorrect 126 ms 716 KB Wrong Answer [4]
36 Incorrect 487 ms 716 KB Wrong Answer [4]
37 Incorrect 323 ms 812 KB Wrong Answer [4]
38 Incorrect 118 ms 716 KB Wrong Answer [4]
39 Incorrect 479 ms 836 KB Wrong Answer [4]
40 Incorrect 48 ms 712 KB Wrong Answer [4]