Submission #1133062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133062		Math4Life2020	Koala Game (APIO17_koala)	C++20	30 / 100	86 ms	484 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;

const int N = 100;
int qtrIdx[N];
int ans[N];
//playRound(a,b): int a[N] (you enter this in), int b[N] (it enters this in)


int minValue(int N1, int W) {
   int a[N],b[N];
   for (int i=0;i<N;i++) {
	   a[i]=1;
   }
   playRound(a,b);
   ll xm = -1;
   for (int i=0;i<N;i++) {
	   if (b[i]==2) {
		   xm = i;
	   }
   }
   for (int i=0;i<N;i++) {
	   a[i]=0;
	   if (i==xm) {
		   a[i]=1;
	   }
   }
   playRound(a,b);
   for (int i=0;i<N;i++) {
	   if (b[i]==0) {
		   return i;
	   }
   }
}


void prc() {
    int a[N],b[N];
    for (int i=0;i<N;i++) {
        a[i]=1;
    }
    playRound(a,b);
    int topHalf[N];
    for (int i=0;i<N;i++) {
        topHalf[i]=(b[i]==2);
        a[i]=b[i];
    }
    playRound(a,b);
   // int qtrIdx[N]; //quarter index:
    //0 -> [1,25] (a=0,b=0)
    //1 -> [26,50] (a=0,b=1)
    //2 -> [51,75] (a=2,b=0)
    //3 -> [76,100] (a=2,b=3)
    for (int i=0;i<N;i++) {
        if (a[i]==0 && b[i]==0) {
            qtrIdx[i]=0;
        }else if (a[i]==0 && b[i]==1) {
            qtrIdx[i]=1;
        }else if (a[i]==2 && b[i]==0) {
            qtrIdx[i]=2;
        }else if (a[i]==2 && b[i]==3) {
            qtrIdx[i]=3;
        }else {
            assert(1==2);
        }
    }
}
int maxValue(int N1, int W) {
    int a[N],b[N];
    prc();
    //put 3 in a: [76,100] -> b: put 50 into 1,2 and then remaining ones go into:
    //[20,25] -> 6, [90,100] -> 4*11=44
    //sumE = 1180
    //[24,25] -> 2, [89,100] -> 4*12=48
    //sumE = 1183
    for (int i=0;i<N;i++) {
        a[i]=3*(qtrIdx[i]==3);
    }
    playRound(a,b);
    vector<int> v1,v2; //[76,88] and [89,100]
    for (int i=0;i<N;i++) {
        if (qtrIdx[i]==3) {
            if (b[i]==4) {
                v2.push_back(i);
            } else {
                v1.push_back(i);
            }
        }
    }
    assert(v2.size()==12);
    for (int i=0;i<N;i++) {
        a[i]=(qtrIdx[i]==2);
    }
    for (int t=0;t<7;t++) {
        a[v1[t]]=1;
    }
    for (int t: v2) {
        a[t]=3;
    }
    playRound(a,b);
    //intervals: [1,25]->0, cost 1, [26,50] cost 25, [51,88] -> 32*1+6*0=32, cost 64+6=70, [89,100]->12*3=36, cost 4
    for (int t: v2) {
        if (b[t]==4) {
            return t;
        }
    } 
}

bool q(int x, int y) { //query p(x)<p(y)
    //first: run 2 queries to partition into quarters
    //if in different quarters -> done.
    int a[N],b[N];
    //prc();
    if (qtrIdx[x]!=qtrIdx[y]) {
        return (qtrIdx[x]<qtrIdx[y]);
    }
    //if in [76,100]: 
    //apply 1 to rest of [76,100] -> cost 2*23=46
    //apply 3 to x,y -> cost 4 for "winner"
    //range [19=76/4,25=100/4]
    //apply 0 to [51,75] -> cost 1*25=25
    //apply 0 to [26,50] -> cost 1*25=25
    //apply 1 to [1,25]
    if (qtrIdx[x]==3) {
        for (ll i=0;i<N;i++) {
            if (qtrIdx[i]==3) {
                if (i==x || i==y) {
                    a[i]=3;
                } else {
                    a[i]=1;
                }
            } else if (qtrIdx[i]==0) {
                a[i]=1;
            } else {
                a[i]=0;
            }
        }
        playRound(a,b);
        return (b[x]<b[y]);
    } else if (qtrIdx[x]==2) {
    //if in [51,75]: 
    //apply 0 to rest of [51,75] -> cost 1*23=23
    //apply 3 to x,y -> cost 4 for "winner"
    //range [>12.5=51/4,~19=75/4]
    //apply 1 to 23, 0 to 2 in rest of [76,100] -> cost 2*23+1*2=48
    //apply 0 to [26,50] -> cost 1*25=25
    //apply 1 to [1,25]
        for (ll i=0;i<N;i++) {
            if (qtrIdx[i]==2) {
                if (i==x || i==y) {
                    a[i]=3;
                } else {
                    a[i]=0;
                }
            } else if (qtrIdx[i]==0 || qtrIdx[i]==3) {
                a[i]=1;
            } else {
                a[i]=0;
            }
        }
        ll n2 = 0;
        for (ll i=0;i<N;i++) {
            if (qtrIdx[i]==3) {
                if (n2<2) {
                    n2++;
                    a[i]=0;
                }
            }
        }
        playRound(a,b);
        return (b[x]<b[y]);
    } else if (qtrIdx[x]==1) {
    //if in [26,50]: 
    //apply 1 to 24 (0 to 1) elements in [76,100] -> cost 51
    //apply 0 to all of [51,75] -> cost 1*25=25
    //apply 2 to x,y -> range [13,25], cost 3
    //apply 0 to rest of [26,50] -> cost 1*23=23
    //apply 2 to [1,25]
        bool tf = 0;
        for (ll i=0;i<N;i++) {
            if (qtrIdx[i]==3) {
                if (!tf) {
                    tf = 1; a[i]=0;
                } else {
                    a[i]=1;
                }
            } else if (qtrIdx[i]==2) {
                a[i]=0;
            } else if (qtrIdx[i]==1) {
                if (i==x || i==y) {
                    a[i]=2;
                } else {
                    a[i]=0;
                }
            } else {
                a[i]=2;
            }
        }
        playRound(a,b);
        return (b[x]<b[y]);
    } else {
        //if in [1,25]: leave just one "hole" open -> GG
        bool tf = 0;
        for (int i=0;i<N;i++) {
            if (qtrIdx[i]==3) {
                if (!tf) {
                    a[i]=0; tf=1;
                } else {
                    a[i]=1;
                }
            } else if (qtrIdx[i]==1 || qtrIdx[i]==2) {
                a[i]=0;
            } else {
                if (i==x || i==y) {
                    a[i]=0;
                } else {
                    a[i]=1;
                }
            }
        }
        playRound(a,b);
        return (b[x]<b[y]);
    }
}

int greaterValue(int N, int W) { //return (P[x]<P[y])
    prc();
    prc();
    return q(0,1);
}

void qstr(vector<ll> velem, ll x0) {
    if (velem.size()==0) {
        return;
    } else if (velem.size()==1) {
        ans[velem[0]]=x0; return;
    }
    mt19937 gen((long long)new char);
    ll xp = velem[gen()%(velem.size())];
    vector<ll> v1,v2;
    for (ll x: velem) {
        if (x==xp) {
            continue;
        }
        bool is2 = q(xp,x);
        if (is2) {
            v2.push_back(x);
        } else {
            v1.push_back(x);
        }
    }
    ans[xp]=x0+v1.size();
    qstr(v1,x0);
    qstr(v2,x0+v1.size()+1);
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    } else {
        prc();
        vector<int> v1;
        for (int i=0;i<N;i++) {
            v1.push_back(i);
        }
        qstr(v1,0);
        for (int i=0;i<N;i++) {
            P[i]=ans[i];
        }
    }
}

Compilation message (stderr)

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
   36 | }
      | ^
koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
  109 | }
      | ^

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 11 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 53