Submission #1072726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072726		ngrace	Koala Game (APIO17_koala)	C++14	73 / 100	48 ms	596 KiB

koala

#include "koala.h"
#include<bits/stdc++.h>
using namespace std;
#define v vector

v<int> query(v<int> q){
    int R[100],B[100];
    for(int i=0;i<q.size();i++) R[i]=q[i];
    playRound(R,B);
    v<int> res(q.size());
    for(int i=0;i<q.size();i++)res[i]=B[i];
    return res;
}

int minValue(int N, int W) {
    v<int> q(N,1);
    v<int> r = query(q);
    q = v<int>(N,0);
    for(int i=0;i<N;i++){
        if(r[i]!=0){
            q[i]=1;
            break;
        }
    }
    r = query(q);
    for(int i=0; i<N; i++){
        if(r[i]==0) return i;
    }
}

int maxValue(int N, int W) {
    v<int> poss;
    for(int i=0;i<N;i++) poss.push_back(i);
    while(poss.size()>1){
        v<int> q(N,0);
        for(int i:poss) q[i] = (W / (int)poss.size());
        v<int> r=query(q);
        v<int> nposs;
        for(int i:poss){
            if(r[i]>(W/(int)poss.size())) nposs.push_back(i);
        }
        poss = nposs;
    }
    return poss[0];
}

int greaterValueInd(int x, int y){
    int l=1,r=9;
    while(l<r){
        int m=(l+r)/2;
        v<int> q(100,0);
        q[x]=m;
        q[y]=m;
        v<int> rr = query(q);
        
        if(rr[x]>m && rr[y]<=m) return 0;
        else if(rr[y]>m && rr[x]<=m) return 1;
        
        if(rr[x]<=m && rr[y]<=m) r=m-1;
        else l=m+1;
    }
    int m=l;
    v<int> q(100,0);
    q[x]=m;
    q[y]=m;
    v<int> rr = query(q);
    
    if(rr[x]>m && rr[y]<=m) return 0;
    else if(rr[y]>m && rr[x]<=m) return 1;
}

int greaterValue(int N, int W) {
    int l=1,r=min(W/2,9);
    while(l<r){
        int m=(l+r)/2;
        v<int> q(100,0);
        q[0]=m;
        q[1]=m;
        v<int> rr = query(q);
        
        if(rr[0]>m && rr[1]<=m) return 0;
        else if(rr[1]>m && rr[0]<=m) return 1;
        
        if(rr[0]<=m && rr[1]<=m) r=m-1;
        else l=m+1;
    }
    int m=l;
    v<int> q(100,0);
    q[0]=m;
    q[1]=m;
    v<int> rr = query(q);
    
    if(rr[0]>m && rr[1]<=m) return 0;
    else if(rr[1]>m && rr[0]<=m) return 1;
}

int comp(int x, int y){
    v<int> q(100, 0);
    q[x] = 100;
    q[y] = 100;
    v<int> r = query(q);
    if(r[x]==0) return 1;
    else return 0;
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        v<int> ind;
        for(int i=0; i<N; i++) ind.push_back(i);
        stable_sort(ind.begin(), ind.end(), comp);
        for(int i=0; i<N; i++) P[ind[i]] = i+1;
    } else {
        v<int> ind;
        for(int i=0; i<N; i++) ind.push_back(i);
        stable_sort(ind.begin(), ind.end(), greaterValueInd);
        for(int i=0; i<N; i++) P[ind[i]] = i+1;
    }
}

Compilation message (stderr)

koala.cpp: In function 'std::vector<int> query(std::vector<int>)':
koala.cpp:8:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for(int i=0;i<q.size();i++) R[i]=q[i];
      |                 ~^~~~~~~~~
koala.cpp:11:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i=0;i<q.size();i++)res[i]=B[i];
      |                 ~^~~~~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:16:17: warning: control reaches end of non-void function [-Wreturn-type]
   16 |     v<int> q(N,1);
      |                 ^
koala.cpp: In function 'int greaterValueInd(int, int)':
koala.cpp:63:19: warning: control reaches end of non-void function [-Wreturn-type]
   63 |     v<int> q(100,0);
      |                   ^
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:88:19: warning: control reaches end of non-void function [-Wreturn-type]
   88 |     v<int> q(100,0);
      |                   ^

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