Submission #1011760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011760		boyliguanhan	Magic Show (APIO24_show)	C++17	35 / 100	29 ms	7596 KiB

Alice

#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;
}

Bob

#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 (stderr)

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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65