oj.uz

Submission #1099140

# Submission time Handle Problem Language Result Execution time Memory
1099140 2024-10-10T15:39:51 Z thangdz2k7 Broken Device (JOI17_broken_device) C++17
0 / 100
 2 ms 1048 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#include "Annalib.h"

using namespace std;

mt19937 rng(145);

const int m = 150, T = 60;

bitset <T> a[m];

long long rnd(long long l, long long r){
    return l + rng() % (r - l + 1);
}

#define Bit(x, i) (x >> i & 1)

void Anna(int N, long long X, int K, int P[]){
    for (int i = 0; i < m; ++ i){
        for (int j = 0; j < T; ++ j) a[i][j] = rnd(0, 1);
    }

    vector <long long> b(m, 0);
    vector <bool> broken(m, 0);
    for (int i = 0; i < K; ++ i) broken[P[i]] = 1;
    for (int i = 0; i < m; ++ i){
        for (int j = 0; j < T; ++ j) if (a[i][j]) b[i] += (1ll << j);
        //cout << b[i] << ' ';
    }

    vector <pair <long long, int>> basis(T, {0, 0});
    for (int i = 0; i < m; ++ i) if (!broken[i]){
        long long x = b[i];
        for (int j = 0; j < T; ++ j) if (Bit(x, j)){
            if (!basis[j].fi) {
                basis[j] = {b[i], i};
                break;
            }
            x ^= basis[j].fi;
        }
    }

    bitset <m> ans;
    long long x = X;
    for (int j = 0; j < T; ++ j) if (Bit(x, j)){
        ans.set(basis[j].se); x ^= basis[j].fi;
    }
    long long xr = 0;
    for (int i = 0; i < m; ++ i) if (ans[i]) xr ^= b[i];
    //cout << xr << endl;
    //cout << x << endl;
    //for (int i = 0; i < m; ++ i) cout << ans[i] << ", ";
    //for (int i = 0; i < m; ++ i) Set(i, ans[i]);
}

//int main(){
//    Anna(150, 10, 0, {});
//}

/*
878674563082620203 262780093936678875 540651479470805762 593907377815262297 380299376663204455 37249183444969754 213872929404555318 459417522222868406 124927146088781769 931340999962379527 408502927193828547 68874064447089923 848112497125255290 644111971581950091 606543736467677644 342622171263008122 602752538031329673 929982292608541156 1120240119647855156 684274015029815656 1084854529836237161 94551196107572299 98449256448120065 1019140510899248010 557681490763462101 759099309321701569 379639721294212678 292435246882131054 923941888985317704 638919318337310612 521390362551843255 654956488965409699 289558298754571428 711351529137365860 681640456206495281 1011309142655713236 27545251691591185 730086068633773200 504459045855498274 540152889488552 37883977193126070 80071456996721047 1050503830218928573 530473883963248092 747913148993728059 837135431368016366 323001234676999611 789766307261509328 141307672000163815 271624504506201057 1134813726655939668 290052932804515620 1079491145687727777 869906479070053232 333300397475108643 987350549402317435 184555010176072213 629696844735926052 935320502152992296 786443130337138888 678830393256726893 463644150754356979 976466349534490705 595365024958622297 31418835627379316 107606196242698013 543834263268952319 79740610311023010 1021972525726416593 1010038715516775410 293070007360781551 877566409560978293 1000079135978211129 871053297576005852 760895601396794724 448527120664982438 699992161384290345 277749830985147420 1126545947647897966 1043789260780182590 594661513820018153 22319307235798650 872808102092988305 746523851683130938 1108158956623257739 77900443046343137 588588723151028519 956585768280924487 394672413436895463 6503519707559569 1021206728253996356 159856868540698981 572020558583778890 1077682212740665518 886018648713341019 515154141805631928 332971394755196792 1144537308531648798 206585655282079984 485693439780766209 637315926660120089 427890372930273141 630547788243137069 891612093758095578 787671229040768936 500822486646418997 848110011952891916 270063337995605829 994831532606671885 227998400932138495 955705690083638444 804130925793479543 296497506825871393 764499736201151160 912263018099209331 435515391488146259 623187692718364028 6324275365611279 517370387976420480 625372128047806784 336196282901039465 123782424290151930 1132516865613568954 52353057821198063 987386711025558674 680578490254475804 622597605976810399 837999254796310098 772445647410586193 827625423569467916 711908648852240972 164437315614580491 175752112594224716 505859465623397102 845718318157234279 214062549622651952 322698739062582069 1121954639726558884 450569074602697192 438378886436455975 1004809804597858547 301326328214333349 824504531048507270 439644303399496948 616070291288493800 311391135971075606 1051893919718841909 755260134088075907 1095428317842260702 272181464928553514
*/

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

using namespace std;

mt19937 rng(145);

const int m = 150, T = 60;

bitset <T> a[m];

long long rnd(long long l, long long r){
    return l + rng() % (r - l + 1);
}

long long Bruno(int N, int A[]){
    long long xr = 0;
    for (int i = 0; i < m; ++ i){
        long long b = 0;
        for (int j = 0; j < T; ++ j){
            int a = rnd(0, 1);
            if (a) b += (1ll << j);
        }
        //cout << b << ' ';
        if (A[i]) xr ^= b;
    }
    return xr;
}

//int main(){
//    vector <int> P = {0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
//    cout << Bruno(150, P);
//}

/*
878674563082620203 262780093936678875 540651479470805762 593907377815262297 380299376663204455 37249183444969754 213872929404555318 459417522222868406 124927146088781769 931340999962379527 408502927193828547 68874064447089923 848112497125255290 644111971581950091 606543736467677644 342622171263008122 602752538031329673 929982292608541156 1120240119647855156 684274015029815656 1084854529836237161 94551196107572299 98449256448120065 1019140510899248010 557681490763462101 759099309321701569 379639721294212678 292435246882131054 923941888985317704 638919318337310612 521390362551843255 654956488965409699 289558298754571428 711351529137365860 681640456206495281 1011309142655713236 27545251691591185 730086068633773200 504459045855498274 540152889488552 37883977193126070 80071456996721047 1050503830218928573 530473883963248092 747913148993728059 837135431368016366 323001234676999611 789766307261509328 141307672000163815 271624504506201057 1134813726655939668 290052932804515620 1079491145687727777 869906479070053232 333300397475108643 987350549402317435 184555010176072213 629696844735926052 935320502152992296 786443130337138888 678830393256726893 463644150754356979 976466349534490705 595365024958622297 31418835627379316 107606196242698013 543834263268952319 79740610311023010 1021972525726416593 1010038715516775410 293070007360781551 877566409560978293 1000079135978211129 871053297576005852 760895601396794724 448527120664982438 699992161384290345 277749830985147420 1126545947647897966 1043789260780182590 594661513820018153 22319307235798650 872808102092988305 746523851683130938 1108158956623257739 77900443046343137 588588723151028519 956585768280924487 394672413436895463 6503519707559569 1021206728253996356 159856868540698981 572020558583778890 1077682212740665518 886018648713341019 515154141805631928 332971394755196792 1144537308531648798 206585655282079984 485693439780766209 637315926660120089 427890372930273141 630547788243137069 891612093758095578 787671229040768936 500822486646418997 848110011952891916 270063337995605829 994831532606671885 227998400932138495 955705690083638444 804130925793479543 296497506825871393 764499736201151160 912263018099209331 435515391488146259 623187692718364028 6324275365611279 517370387976420480 625372128047806784 336196282901039465 123782424290151930 1132516865613568954 52353057821198063 987386711025558674 680578490254475804 622597605976810399 837999254796310098 772445647410586193 827625423569467916 711908648852240972 164437315614580491 175752112594224716 505859465623397102 845718318157234279 214062549622651952 322698739062582069 1121954639726558884 450569074602697192 438378886436455975 1004809804597858547 301326328214333349 824504531048507270 439644303399496948 616070291288493800 311391135971075606 1051893919718841909 755260134088075907 1095428317842260702 272181464928553514
*/

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 784 KB Wrong Answer [4]
2 Incorrect 0 ms 796 KB Wrong Answer [4]
3 Incorrect 1 ms 796 KB Wrong Answer [4]
4 Incorrect 1 ms 784 KB Wrong Answer [4]
5 Incorrect 0 ms 784 KB Wrong Answer [4]
6 Incorrect 0 ms 796 KB Wrong Answer [4]
7 Incorrect 1 ms 796 KB Wrong Answer [4]
8 Incorrect 1 ms 796 KB Wrong Answer [4]
9 Incorrect 1 ms 796 KB Wrong Answer [4]
10 Incorrect 1 ms 792 KB Wrong Answer [4]
11 Incorrect 1 ms 796 KB Wrong Answer [4]
12 Incorrect 1 ms 796 KB Wrong Answer [4]
13 Incorrect 0 ms 792 KB Wrong Answer [4]
14 Incorrect 0 ms 1048 KB Wrong Answer [4]
15 Incorrect 0 ms 784 KB Wrong Answer [4]
16 Incorrect 0 ms 784 KB Wrong Answer [4]
17 Incorrect 0 ms 784 KB Wrong Answer [4]
18 Incorrect 0 ms 784 KB Wrong Answer [4]
19 Incorrect 1 ms 784 KB Wrong Answer [4]
20 Incorrect 1 ms 796 KB Wrong Answer [4]
21 Incorrect 1 ms 784 KB Wrong Answer [4]
22 Incorrect 1 ms 776 KB Wrong Answer [4]
23 Incorrect 0 ms 784 KB Wrong Answer [4]
24 Incorrect 0 ms 796 KB Wrong Answer [4]
25 Incorrect 0 ms 784 KB Wrong Answer [4]
26 Incorrect 0 ms 780 KB Wrong Answer [4]
27 Incorrect 1 ms 796 KB Wrong Answer [4]
28 Incorrect 0 ms 796 KB Wrong Answer [4]
29 Incorrect 1 ms 796 KB Wrong Answer [4]
30 Incorrect 1 ms 796 KB Wrong Answer [4]
31 Incorrect 0 ms 796 KB Wrong Answer [4]
32 Incorrect 1 ms 792 KB Wrong Answer [4]
33 Incorrect 1 ms 796 KB Wrong Answer [4]
34 Incorrect 2 ms 1036 KB Wrong Answer [4]
35 Incorrect 0 ms 796 KB Wrong Answer [4]
36 Incorrect 1 ms 792 KB Wrong Answer [4]
37 Incorrect 0 ms 784 KB Wrong Answer [4]
38 Incorrect 1 ms 796 KB Wrong Answer [4]
39 Incorrect 1 ms 796 KB Wrong Answer [4]
40 Incorrect 1 ms 784 KB Wrong Answer [4]