oj.uz

Submission #1011760

# Submission time Handle Problem Language Result Execution time Memory
1011760 2024-07-01T08:05:04 Z boyliguanhan Magic Show (APIO24_show) C++17
35 / 100
 29 ms 7596 KB 
#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
set<int> v[5000];
vector<int> VV(4999),v2[5000];
int capacity[5000],given[5000];
mt19937 rng(1987042837);
void gen(){
    int sum=0;
    for(int i=2;i<5000;i++)
        sum+=capacity[i]=log2(i-1);
    sum/=30;
    vector<int>Z(30),Z2(4998);
    iota(Z.begin(),Z.end(),0);
    iota(Z2.begin(),Z2.end(),2);
    iota(VV.begin(),VV.end(),1);
    shuffle(Z.begin(),Z.end(),rng);
    shuffle(VV.begin(),VV.end(),rng);
    for(auto j:Z){
        int x=sum;
        shuffle(Z2.begin(),Z2.end(),rng);
        for(auto i:Z2)if(capacity[i]*!v[i].count(j)*x)
            capacity[i]--,v[i].insert(j),x--;
    }
    for(auto i:Z2)while(capacity[i]){
        vector<int>VVV(30);
        iota(VVV.begin(),VVV.end(),0);
        shuffle(VVV.begin(),VVV.end(),rng);
        int x=-1;
        for(auto j:VVV)
            if(!v[i].count(j)){
                x=j;
                break;
            }
        v[i].insert(x);
        capacity[i]--;
    }
    for(auto i:Z2)
        for(auto j:v[i])
            v2[i].push_back(j);
    for(auto i:Z2)shuffle(v2[i].begin(),v2[i].end(),rng);
}
std::vector<std::pair<int,int>> Alice(){
    gen();
    long long x=setN(4999);
    vector<pair<int,int>>ans;
    for(int i=2;i<5e3;i++)for(auto j:v2[i])
        given[i]=given[i]*2+(x>>j&1);
    for(int i=2;i<5e3;i++){
        int a=VV[given[i]],b=VV[i-1];
        if(rng()%2)
            swap(a,b);
        ans.push_back({a,b});
    }
    shuffle(ans.begin(),ans.end(),rng);
    return ans;
}

#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().
set<int> vv[5000];
vector<int> VVV(4999),v2v[5000];
int cap[5000],pos[5000];
mt19937 rng2(1987042837);
void gen2(){
    int sum=0;
    for(int i=2;i<5000;i++)
        sum+=cap[i]=log2(i-1);
    sum/=30;
  vector<int>Z(30),Z2(4998);
    iota(Z.begin(),Z.end(),0);
    iota(Z2.begin(),Z2.end(),2);
    iota(VVV.begin(),VVV.end(),1);
    shuffle(Z.begin(),Z.end(),rng2);
    shuffle(VVV.begin(),VVV.end(),rng2);
    for(int i=0;i<4999;i++)
        pos[VVV[i]]=i;
    for(auto j:Z){
        int x=sum;
        shuffle(Z2.begin(),Z2.end(),rng2);
        for(auto i:Z2)if(cap[i]*!vv[i].count(j)*x)
            cap[i]--,vv[i].insert(j),x--;
    }
    for(auto i:Z2)while(cap[i]){
        vector<int>VVV(30);
        iota(VVV.begin(),VVV.end(),0);
        shuffle(VVV.begin(),VVV.end(),rng2);
        int x=-1;
        for(auto j:VVV)
            if(!vv[i].count(j)){
                x=j;
                break;
            }
        vv[i].insert(x);
        cap[i]--;
    }
    for(auto i:Z2)
        for(auto j:vv[i])
            v2v[i].push_back(j);
    for(auto i:Z2)shuffle(v2v[i].begin(),v2v[i].end(),rng2);
}
long long Bob(std::vector<std::pair<int,int>> V){
    long long ans=0;
    gen2();
    int tot=0;
    for(auto i:V){
        auto[a,b]=i;
        if(pos[a]>pos[b])
            swap(a,b);
        int k=pos[b]+1,q=pos[a];
        vector<int>v22=v2v[k];
        reverse(v22.begin(),v22.end());
        for(auto i:v22){
            ans|=(q&1ll)<<i;
            q/=2;
        }
    }
    return max(ans,1ll);
}

Compilation message

Alice.cpp: In function 'void gen()':
Alice.cpp:24:52: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
   24 |         for(auto i:Z2)if(capacity[i]*!v[i].count(j)*x)
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~^~

Bob.cpp: In function 'void gen2()':
Bob.cpp:26:48: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
   26 |         for(auto i:Z2)if(cap[i]*!vv[i].count(j)*x)
      |                          ~~~~~~~~~~~~~~~~~~~~~~^~
Bob.cpp: In function 'long long int Bob(std::vector<std::pair<int, int> >)':
Bob.cpp:50:9: warning: unused variable 'tot' [-Wunused-variable]
   50 |     int tot=0;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7248 KB Correct.
2 Correct 22 ms 7472 KB Correct.
3 Correct 22 ms 7412 KB Correct.
4 Correct 26 ms 7596 KB Correct.
5 Correct 25 ms 7480 KB Correct.
6 Correct 24 ms 7280 KB Correct.
7 Correct 28 ms 7400 KB Correct.
8 Correct 23 ms 7440 KB Correct.
9 Correct 22 ms 7480 KB Correct.
10 Correct 27 ms 7448 KB Correct.
11 Correct 24 ms 7396 KB Correct.
12 Correct 22 ms 7464 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7248 KB Correct.
2 Correct 22 ms 7472 KB Correct.
3 Correct 22 ms 7412 KB Correct.
4 Correct 26 ms 7596 KB Correct.
5 Correct 25 ms 7480 KB Correct.
6 Correct 24 ms 7280 KB Correct.
7 Correct 28 ms 7400 KB Correct.
8 Correct 23 ms 7440 KB Correct.
9 Correct 22 ms 7480 KB Correct.
10 Correct 27 ms 7448 KB Correct.
11 Correct 24 ms 7396 KB Correct.
12 Correct 22 ms 7464 KB Correct.
13 Correct 24 ms 7488 KB Correct.
14 Correct 22 ms 7452 KB Correct.
15 Correct 23 ms 7476 KB Correct.
16 Correct 24 ms 7412 KB Correct.
17 Correct 29 ms 7396 KB Correct.
18 Correct 23 ms 7456 KB Correct.
19 Correct 24 ms 7476 KB Correct.
20 Correct 22 ms 7476 KB Correct.
21 Correct 22 ms 7392 KB Correct.
22 Correct 24 ms 7476 KB Correct.
23 Correct 26 ms 7468 KB Correct.
24 Correct 20 ms 7480 KB Correct.

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7248 KB Correct.
2 Correct 22 ms 7472 KB Correct.
3 Correct 22 ms 7412 KB Correct.
4 Correct 26 ms 7596 KB Correct.
5 Correct 25 ms 7480 KB Correct.
6 Correct 24 ms 7280 KB Correct.
7 Correct 28 ms 7400 KB Correct.
8 Correct 23 ms 7440 KB Correct.
9 Correct 22 ms 7480 KB Correct.
10 Correct 27 ms 7448 KB Correct.
11 Correct 24 ms 7396 KB Correct.
12 Correct 22 ms 7464 KB Correct.
13 Correct 24 ms 7488 KB Correct.
14 Correct 22 ms 7452 KB Correct.
15 Correct 23 ms 7476 KB Correct.
16 Correct 24 ms 7412 KB Correct.
17 Correct 29 ms 7396 KB Correct.
18 Correct 23 ms 7456 KB Correct.
19 Correct 24 ms 7476 KB Correct.
20 Correct 22 ms 7476 KB Correct.
21 Correct 22 ms 7392 KB Correct.
22 Correct 24 ms 7476 KB Correct.
23 Correct 26 ms 7468 KB Correct.
24 Correct 20 ms 7480 KB Correct.
25 Incorrect 24 ms 7484 KB Incorrect answer.
26 Halted 0 ms 0 KB -