Submission #1190491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190491		KhoaDuy	Alice, Bob, and Circuit (APIO23_abc)	C++17	100 / 100	844 ms	535076 KiB

abc

#include<bits/stdc++.h>
using namespace std;
#include "abc.h"
//CHANGE THIS LINE
const int LEN=1024;
string toBin(int x,int len){
    string s="";
    while(x>0){
        s+=((x&1)+'0');
        x>>=1;
    }
    while(s.length()<len){
        s+='0';
    }
    reverse(s.begin(),s.end());
    return s;
}
void DFS(int u,int col[],vector<vector<int>> &graph){
    for(int v:graph[u]){
        if(col[v]==-1){
            col[v]=(col[u]^1);
            DFS(v,col,graph);
        }
        else{
            assert(col[v]==(col[u]^1));
        }
    }
}
void getseq(vector<int> &p,string &s){
    if(p.size()==1){
        return;
    }
    int n=p.size();
    vector<vector<int>> graph(n);
    for(int i=0;i<n/2;i++){
        graph[i].push_back(i+n/2);
        graph[i+n/2].push_back(i);
        graph[p[i]].push_back(p[i+n/2]);
        graph[p[i+n/2]].push_back(p[i]);
    }
    int col[n];
    memset(col,-1,sizeof(col));
    for(int i=0;i<n;i++){
        if(col[i]==-1){
            col[i]=0;
            DFS(i,col,graph);
        }
    }
    vector<int> le(n/2),ri(n/2);
    for(int i=0;i<n/2;i++){
        s+=(col[p[i]]+'0');
        if(col[p[i]]){
            swap(p[i],p[i+n/2]);
        }
        le[i]=(p[i]%(n/2));
        ri[i]=(p[i+n/2]%(n/2));
    }
    getseq(le,s),getseq(ri,s);
    for(int i=0;i<n/2;i++){
        s+=(col[i]+'0');
    }
}
int alice(const int n,const char names[][5],const unsigned short numbers[],bool outputs_alice[]){
    int power[5];
    power[1]=0;
    int breh=1;
    for(int i=2;i<5;i++){
        breh*=26;
        power[i]=power[i-1]+breh;
    }
    string s="";
    vector<pair<int,int>> order(LEN);
    for(int i=0;i<n;i++){
        int x=0;
        for(int j=0;j<5;j++){
            if(names[i][j]=='\0'){
                x+=power[j];
                break;
            }
            x=x*26+(names[i][j]-'a');
        }
        order[i]={x,i};
    }
    for(int i=n;i<LEN;i++){
        order[i]={(1<<19)-1-(i-n),i};
    }
    sort(order.begin(),order.end());
    vector<int> p(LEN);
    for(int i=0;i<LEN;i++){
        p[i]=order[i].second;
        if(i<n){
            s+=toBin(order[i].first,19);
            s+=toBin(order[i].first,19);
            if(order[i].second<n){
                s+=toBin(numbers[order[i].second],16);
            }
            else{
                s+=toBin(0,16);
            }
            s+=toBin(0,1);
        }
    }
    int old=s.length();
    getseq(p,s);
    for(int i=0;i<s.length();i++){
        if(s[i]=='1'){
            outputs_alice[i]=true;
        }
        else{
            outputs_alice[i]=false;
        }
    }
    return s.length();
}
bool cmp(pair<pair<int,int>,int> &a,pair<pair<int,int>,int> &b){
    return (a.first.second<b.first.second);
}
int bob(const int m,const char senders[][5],const char recipients[][5],bool outputs_bob[]){
    int power[5];
    power[1]=0;
    int breh=1;
    for(int i=2;i<5;i++){
        breh*=26;
        power[i]=power[i-1]+breh;
    }
    string s="";
    vector<pair<pair<int,int>,int>> order(LEN);
    for(int i=0;i<m;i++){
        int x=0,y=0;
        for(int j=0;j<5;j++){
            if(senders[i][j]=='\0'){
                x+=power[j];
                break;
            }
            x=x*26+(senders[i][j]-'a');
        }
        for(int j=0;j<5;j++){
            if(recipients[i][j]=='\0'){
                y+=power[j];
                break;
            }
            y=y*26+(recipients[i][j]-'a');
        }
        order[i]={{x,y},i};
    }
    for(int i=m;i<LEN;i++){
        order[i]={{(1<<19)-1,(1<<19)-1},i};
    }
    sort(order.begin(),order.end(),cmp);
    int val[LEN];
    for(int i=0;i<order.size();i++){
        val[order[i].second]=i;
    }
    sort(order.begin(),order.end());
    vector<int> p(LEN);
    for(int i=0;i<LEN;i++){
        p[i]=val[order[i].second];
        if(i<m){
            s+=toBin(order[i].first.first,19);
            s+=toBin(order[i].first.second,19);
            s+=toBin(0,16);
            s+=toBin(1,1);
        }
    }
    getseq(p,s);
    for(int i=0;i<s.length();i++){
        if(s[i]=='1'){
            outputs_bob[i]=true;
        }
        else{
            outputs_bob[i]=false;
        }
    }
    return s.length();
}
// you may find the definitions useful
const int OP_ZERO    = 0;  // f(OP_ZERO,    x0, x1) = 0
const int OP_NOR     = 1;  // f(OP_NOR,     x0, x1) = !(x0 || x1)
const int OP_GREATER = 2;  // f(OP_GREATER, x0, x1) = (x0 > x1)
const int OP_NOT_X1  = 3;  // f(OP_NOT_X1,  x0, x1) = !x1
const int OP_LESS    = 4;  // f(OP_LESS,    x0, x1) = (x0 < x1)
const int OP_NOT_X0  = 5;  // f(OP_NOT_X0,  x0, x1) = !x0
const int OP_XOR     = 6;  // f(OP_XOR,     x0, x1) = (x0 ^ x1)
const int OP_NAND    = 7;  // f(OP_NAND,    x0, x1) = !(x0 && x1)
const int OP_AND     = 8;  // f(OP_AND,     x0, x1) = (x0 && x1)
const int OP_EQUAL   = 9;  // f(OP_EQUAL,   x0, x1) = (x0 == x1)
const int OP_X0      = 10; // f(OP_X0,      x0, x1) = x0
const int OP_GEQ     = 11; // f(OP_GEQ,     x0, x1) = (x0 >= x1)
const int OP_X1      = 12; // f(OP_X1,      x0, x1) = x1
const int OP_LEQ     = 13; // f(OP_LEQ,     x0, x1) = (x0 <= x1)
const int OP_OR      = 14; // f(OP_OR,      x0, x1) = (x0 || x1)
const int OP_ONE     = 15; // f(OP_ONE,     x0, x1) = 1
int tim;
const int LIMIT=2*1e7;
int Operations[LIMIT],Operands[LIMIT][2];
//int val[LIMIT];
vector<int> make(int len){
    vector<int> v(len);
    for(int i=0;i<len;i++){
        v[i]=tim+i;
    }
    tim+=len;
    return v;
}
int makeone(){
    Operands[tim][0]=-2,Operands[tim][1]=-2,Operations[tim]=-2;
    tim++;
    assert(tim<=LIMIT);
    return tim-1;
}
struct tup{
    vector<int> u,v,w,t;
};
int eval(int x0,int x1,int p){
    int temp=(p/(1<<(x0+2*x1)));
    return (temp&1);
}
void init(int idx,int a,int b,int ope){
    if(ope==-1){
        assert(a==-1&&b==-1);
    }
    else{
        assert(ope>=0&&ope<16&&idx>a&&idx>b&&a>=0&&b>=0);
        //val[idx]=eval(val[a],val[b],ope);
    }
    Operands[idx][0]=a,Operands[idx][1]=b,Operations[idx]=ope;
}
/*int print(vector<int> a){
    int x=0;
    for(int i=0;i<a.size();i++){
        x=(x*2+val[a[i]]);
    }
    return x;
}*/
int ZeroId,OneId;
int cmpGRE(vector<int> a,vector<int> a2,vector<int> b,vector<int> b2){
    for(int i=0;i<a2.size();i++){
        a.push_back(a2[i]);
    }
    for(int i=0;i<b2.size();i++){
        b.push_back(b2[i]);
    }
    assert(a.size()==b.size());
    int equ=OneId;
    int gre=ZeroId;
    for(int i=0;i<a.size();i++){
        int cmp1=makeone();
        init(cmp1,a[i],b[i],OP_GREATER);
        int cmp2=makeone();
        init(cmp2,a[i],b[i],OP_EQUAL);
        int tmp=makeone();
        init(tmp,equ,cmp1,OP_AND);
        int nxtGre=makeone();
        init(nxtGre,gre,tmp,OP_OR);
        int nxtEqu=makeone();
        init(nxtEqu,equ,cmp2,OP_AND);
        equ=nxtEqu,gre=nxtGre;
    }
    return gre;
}
vector<int> opeAND(vector<int> &a,int b){
    vector<int> nxt(a.size());
    for(int i=0;i<a.size();i++){
        nxt[i]=makeone();
        init(nxt[i],a[i],b,OP_AND);
    }
    return nxt;
}
vector<int> opeOR(vector<int> &a,vector<int> &b){
    assert(a.size()==b.size());
    vector<int> nxt(a.size());
    for(int i=0;i<a.size();i++){
        nxt[i]=makeone();
        init(nxt[i],a[i],b[i],OP_OR);
    }
    return nxt;
}
vector<int> opeXOR(vector<int> &a,vector<int> &b){
    assert(a.size()==b.size());
    vector<int> nxt(a.size());
    for(int i=0;i<a.size();i++){
        nxt[i]=makeone();
        init(nxt[i],a[i],b[i],OP_XOR);
    }
    return nxt;
}
void swapCond(vector<int> &a,vector<int> &b,int cond){
    assert(a.size()==b.size());
    vector<int> c=opeXOR(a,b);
    c=opeAND(c,cond);
    a=opeXOR(a,c),b=opeXOR(b,c);
}
void mergeSort(vector<tup> &curr,int x,int y,int d,vector<int> &record){
    if(x+d==y){
        int cond=cmpGRE(curr[x].u,curr[x].t,curr[y].u,curr[y].t);
        record.push_back(cond);
        swapCond(curr[x].u,curr[y].u,cond);
        swapCond(curr[x].v,curr[y].v,cond);
        swapCond(curr[x].w,curr[y].w,cond);
        swapCond(curr[x].t,curr[y].t,cond);
        return;
    }
    mergeSort(curr,x,y,2*d,record),mergeSort(curr,x+d,y+d,2*d,record);
    for(x=x+d;x+d<curr.size();x+=2*d){
        y=x+d;
        int cond=cmpGRE(curr[x].u,curr[x].t,curr[y].u,curr[y].t);
        record.push_back(cond);
        swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
        swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
    }
}
void undo(vector<tup> &curr,int X,int Y,int d,vector<int> &record){
    if(X+d==Y){
        int x=X,y=Y;
        assert(!record.empty());
        int cond=record.back();
        record.pop_back();
        swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
        swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
        return;
    }
    vector<pair<int,int>> bruh;
    for(int x=X+d;x+d<curr.size();x+=2*d){
        bruh.push_back({x,x+d});
    }
    for(int i=bruh.size()-1;i>=0;i--){
        int x=bruh[i].first,y=bruh[i].second;
        assert(!record.empty());
        int cond=record.back();
        record.pop_back();
        swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
        swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
    }
    undo(curr,X+d,Y+d,2*d,record);
    undo(curr,X,Y,2*d,record);
}
void bijec(int l,int r,vector<tup> &curr,vector<int> &record){
    if(l==r){
        return;
    }
    int mid=((l+r)>>1);
    for(int x=l;x<=mid;x++){
        int y=x-l+mid+1;
        assert(!record.empty());
        int cond=record.back();
        record.pop_back();
        swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
        swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
    }
    bijec(l,mid,curr,record);
    bijec(mid+1,r,curr,record);
    for(int x=l;x<=mid;x++){
        int y=x-l+mid+1;
        assert(!record.empty());
        int cond=record.back();
        record.pop_back();
        swapCond(curr[x].u,curr[y].u,cond),swapCond(curr[x].v,curr[y].v,cond);
        swapCond(curr[x].w,curr[y].w,cond),swapCond(curr[x].t,curr[y].t,cond);
    }
}
vector<int> opeADD(vector<int> &a,vector<int> &b){
    assert(a.size()==b.size());
    vector<int> rem(a.size()),res(a.size());
    rem[a.size()-1]=ZeroId;
    for(int i=a.size()-1;i>=0;i--){
        int tmp=makeone();
        init(tmp,a[i],b[i],OP_XOR);
        res[i]=makeone();
        init(res[i],tmp,rem[i],OP_XOR);
        if(i>0){
            int tmp2=makeone();
            init(tmp2,tmp,rem[i],OP_AND);
            tmp=makeone();
            init(tmp,a[i],b[i],OP_AND);
            rem[i-1]=makeone();
            init(rem[i-1],tmp,tmp2,OP_OR);
        }
    }
    return res;
}
int circuit(const int la,const int lb,int operations[],int operands[][2],int outputs_circuit[][16]){
    for(int i=0;i<la+lb;i++){
        init(i,-1,-1,-1);
    }
    string breh="";
    vector<int> permu(LEN);
    for(int i=0;i<LEN;i++){
        permu[i]=i;
    }
    getseq(permu,breh);
    const int counter=19+19+16+1;
    int n=(la-breh.length())/counter,m=(lb-breh.length())/counter;
    vector<tup> curr(2*LEN);
    for(int i=0;i<2*LEN;i++){
        curr[i].u.resize(19),curr[i].v.resize(19),curr[i].w.resize(16),curr[i].t.resize(1);
    }
    tim=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<19;j++){
            curr[i].u[j]=tim+j,curr[i].v[j]=tim+19+j;
            if(j<16){
                curr[i].w[j]=tim+38+j;
            }
            if(j==0){
                curr[i].t[j]=tim+54+j;
            }
        }
        tim+=counter;
    }
    tim=la;
    for(int i=LEN;i<LEN+m;i++){
        for(int j=0;j<19;j++){
            curr[i].u[j]=tim+j,curr[i].v[j]=tim+19+j;
            if(j<16){
                curr[i].w[j]=tim+38+j;
            }
            if(j==0){
                curr[i].t[j]=tim+54+j;
            }
        }
        tim+=counter;
    }
    tim=la+lb;
    OneId=makeone();
    init(OneId,0,1,OP_ONE);
    ZeroId=makeone();
    init(ZeroId,0,1,OP_ZERO);
    for(int i=n;i<LEN;i++){
        int x=(1<<19)-1-(i-n);
        for(int j=0;j<19;j++){
            if(x&(1<<(18-j))){
                curr[i].u[j]=OneId;
                curr[i].v[j]=OneId;
            }
            else{
                curr[i].u[j]=ZeroId;
                curr[i].v[j]=ZeroId;
            }
            if(j<16){
                curr[i].w[j]=ZeroId;
                if(j==0){
                    curr[i].t[j]=ZeroId;
                }
            }
        }
    }
    for(int i=LEN+m;i<2*LEN;i++){
        int x=(1<<19)-1;
        for(int j=0;j<19;j++){
            if(x&(1<<(18-j))){
                curr[i].u[j]=OneId;
                curr[i].v[j]=OneId;
            }
            else{
                curr[i].u[j]=ZeroId;
                curr[i].v[j]=ZeroId;
            }
            if(j<16){
                curr[i].w[j]=ZeroId;
                if(j==0){
                    curr[i].t[j]=OneId;
                }
            }
        }
    }
    vector<int> record;
    int OLD=tim;
    mergeSort(curr,0,LEN,1,record);
    vector<int> sum(16);
    for(int i=0;i<sum.size();i++){
        sum[i]=ZeroId;
    }
    for(int i=0;i<curr.size();i++){
        if(i>0){
            int cond=cmpGRE(curr[i].u,{},curr[i-1].u,{});
            int inv=makeone();
            init(inv,0,cond,OP_NOT_X1);
            sum=opeAND(sum,inv);
        }
        sum=opeOR(sum,curr[i].w);
        curr[i].w=sum;
    }
    undo(curr,0,LEN,1,record);
    for(int i=la+counter*m;i<la+lb;i++){
        record.push_back(i);
    }
    reverse(record.begin(),record.end());
    bijec(LEN,2*LEN-1,curr,record);
    for(int i=0;i<curr.size();i++){
        swap(curr[i].u,curr[i].v);
    }
    mergeSort(curr,0,LEN,1,record);
    for(int i=0;i<curr.size();i++){
        swap(curr[i].u,curr[i].v);
    }
    sum.clear(),sum.resize(16);
    for(int i=0;i<sum.size();i++){
        sum[i]=ZeroId;
    }
    for(int i=curr.size()-1;i>=0;i--){
        if(i+1<curr.size()){
            int cond=cmpGRE(curr[i+1].v,{},curr[i].v,{});
            int inv=makeone();
            init(inv,0,cond,OP_NOT_X1);
            sum=opeAND(sum,inv);
        }
        vector<int> old=curr[i].w;
        curr[i].w=sum;
        sum=opeADD(sum,old);
    }
    undo(curr,0,LEN,1,record);
    for(int i=counter*n;i<la;i++){
        record.push_back(i);
    }
    reverse(record.begin(),record.end());
    bijec(0,LEN-1,curr,record);
    assert(tim<=LIMIT);
    for(int i=0;i<tim;i++){
        operands[i][0]=Operands[i][0],operands[i][1]=Operands[i][1];
        operations[i]=Operations[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<16;j++){
            outputs_circuit[i][15-j]=curr[i].w[j];
        }
    }
    return tim;
}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24
• Subtask 6: 6 / 6
• Subtask 7: 18 / 18
• Subtask 8: 10 / 10
• Subtask 9: 6 / 6