Submission #1190254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190254		KhoaDuy	Alice, Bob, and Circuit (APIO23_abc)	C++17	4 / 100	736 ms	569188 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);
        }
    }
    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<<16)-1,(1<<16)-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];
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;
};
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);
    }
    Operands[idx][0]=a,Operands[idx][1]=b,Operations[idx]=ope;
}
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;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;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);
    sum.clear(),sum.resize(16);
    for(int i=0;i<sum.size();i++){
        sum[i]=ZeroId;
    }
    for(int i=0;i<curr.size();i++){
        swap(curr[i].u,curr[i].v);
    }
    for(int i=curr.size()-1;i>=0;i--){
        if(i+1<curr.size()){
            int cond=cmpGRE(curr[i+1].v,{},curr[i].v,{});
            sum=opeAND(sum,cond);
        }
        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;
}
/*const int MAX_LA = 100000;
const int MAX_LB = 100000;
const int MAX_L = 20000000;
void fatal(const string& msg) {
    cerr << msg << endl;
    exit(1);
}

void ensureImpl(bool condition, const char* conditionStr) {
    if (condition)
        return;
    fatal("Condition does not satisfy: " + string(conditionStr));
}

#define ensure(x...) ensureImpl(x, #x)

template <typename F>
void timed(const string& name, const F& func) {
    cerr << "Running " << name << "..." << endl;
    auto start = chrono::high_resolution_clock::now();
    func();
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::nanoseconds>(end - start);
    cerr << name << " took " << fixed << setprecision(6) << (double) duration.count() / 1e9 << " seconds" << endl;
}

int main() {
    // ==================== Read Input ====================
    int n, m;
    cin >> n >> m;
    ensure(0 <= n && n <= 700);
    ensure(0 <= m && m <= 1000);

    auto readUshort = [&]() {
        string s;
        cin >> s;
        stringstream ss(s);
        unsigned short x;
        ss >> x;
        if (s != to_string(x))
            fatal("Invalid input for unsigned short: " + s);
        return x;
    };
    vector<pair<string, unsigned short>> students;
    map<string, unsigned short> studentsMap;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        if (name.empty())
            fatal("Expected name");
        if (name.size() > 4)
            fatal("Name too long: " + name);
        bool ok = true;
        for (char c : name)
            if (c < 'a' || c > 'z')
                ok = false;
        if (!ok)
            fatal("Invalid name: " + name);
        unsigned short number = readUshort();
        students.emplace_back(name, number);

        if (studentsMap.count(name))
            fatal("Duplicate name: " + name);
        studentsMap[name] = number;
    }

    auto readExistingName = [&] {
        string name;
        cin >> name;
        if (!studentsMap.count(name))
            fatal("Unknown name in Bob's input: " + name);
        return name;
    };
    vector<pair<string, string>> messages;
    for (int i = 0; i < m; i++) {
        string sender = readExistingName();
        string recipient = readExistingName();
        messages.emplace_back(sender, recipient);
    }

    // ==================== Call Alice ====================
    char (*aliceNames)[5] = new char[n][5];
    memset(aliceNames[0], 0, n * 5);
    unsigned short* aliceNumbers = new unsigned short[n];
    bool* aliceOutputs = new bool[MAX_LA];
    memset(aliceOutputs, 0, MAX_LA);
    for (int i = 0; i < n; i++) {
        strcpy(aliceNames[i], students[i].first.c_str());
        aliceNumbers[i] = students[i].second;
    }
    int la;
    timed("Alice", [&]() {
        la = alice(n, aliceNames, aliceNumbers, aliceOutputs);
    });
    cerr << "la = " << la << endl;
    ensure(0 <= la && la <= MAX_LA);

    // ==================== Call Bob ====================
    char (*bobSenders)[5] = new char[m][5];
    memset(bobSenders[0], 0, m * 5);
    char (*bobRecipients)[5] = new char[m][5];
    memset(bobRecipients[0], 0, m * 5);
    bool* bobOutputs = new bool[MAX_LB];
    memset(bobOutputs, 0, MAX_LB);
    for (int i = 0; i < m; i++) {
        strcpy(bobSenders[i], messages[i].first.c_str());
        strcpy(bobRecipients[i], messages[i].second.c_str());
    }
    int lb;
    timed("Bob", [&]() {
        lb = bob(m, bobSenders, bobRecipients, bobOutputs);
    });
    cerr << "lb = " << lb << endl;
    ensure(0 <= lb && lb <= MAX_LB);
    // ==================== Call Circuit ====================
    int* circuitOperations = new int[MAX_L];
    memset(circuitOperations, 0xff, MAX_L * sizeof(int));
    int (*circuitOperands)[2] = new int[MAX_L][2];
    memset(circuitOperands[0], 0xff, MAX_L * 2 * sizeof(int));
    int (*circuitOutputs)[16] = new int[n][16];
    memset(circuitOutputs[0], 0xff, n * 16 * sizeof(int));
    int l;
    timed("Circuit", [&]() {
        l = circuit(la, lb, circuitOperations, circuitOperands, circuitOutputs);
    });
    cerr << "l = " << l << endl;
    ensure(0 <= l && l <= MAX_L);

    bool* values = new bool[l];
    memcpy(values, aliceOutputs, la * sizeof(bool));
    memcpy(values + la, bobOutputs, lb * sizeof(bool));
    for (int i = la + lb; i < l; i++) {
        int op = circuitOperations[i];
        if (op < 0 || op > 15)
            fatal("Invalid operation: " + to_string(op) + " at Circuit index " + to_string(i));
        int a = circuitOperands[i][0];
        int b = circuitOperands[i][1];
        if (a < 0 || a >= i)
            fatal("Invalid operand 0: " + to_string(a) + " at Circuit index " + to_string(i));
        if (b < 0 || b >= i)
            fatal("Invalid operand 1: " + to_string(b) + " at Circuit index " + to_string(i));
        bool x0 = values[a];
        bool x1 = values[b];
        values[i] = op >> (x0 + 2 * x1) & 1;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < 16; j++)
            if (circuitOutputs[i][j] < 0 || circuitOutputs[i][j] >= l)
                fatal("Invalid output: " + to_string(circuitOutputs[i][j]) + " at Circuit index " + to_string(i) + ", " + to_string(j));
    vector<unsigned short> answers;
    for (int i = 0; i < n; i++) {
        unsigned short ans = 0;
        for (int j = 0; j < 16; j++)
            ans |= (unsigned short) values[circuitOutputs[i][j]] << j;
        answers.push_back(ans);
    }

    // ==================== Calculate Reference Answer ====================
    map<string, unsigned short> referenceMap;
    for (int i = 0; i < m; i++)
        referenceMap[messages[i].second] += studentsMap[messages[i].first];
    bool ok = true;
    for (int i = 0; i < n; i++)
        if (answers[i] != referenceMap[students[i].first]) {
            ok = false;
            cerr << "Wrong answer for " << students[i].first << ": expected " << referenceMap[students[i].first] << ", but got " << answers[i] << endl;
        }
    if (ok)
        cerr << "Your answer seems correct" << endl;

    // ==================== Print Answer ====================
    for (int i = 0; i < n; i++)
        cout << answers[i] << '\n';

    return 0;
}*/

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