Submission #111817

#	Time	Username	Problem	Language	Result	Execution time	Memory
111817		dndhk	Koala Game (APIO17_koala)	C++14	70 / 100	114 ms	892 KiB

koala

#include "koala.h"
#include <algorithm>
#include <vector>

#define pb push_back

using namespace std;

int B[100], R[100];



int minValue(int N, int W) {
    B[99] = 1;
    playRound(B, R);
    for(int i=0; i<N; i++){
        if(R[i]==0){
            return i;
        }
    }
    return 99;
}

int maxValue(int N, int W) {
    for(int i=0; i<N; i++){
        B[i] = 1;
    }
    playRound(B, R);
    for(int i=0; i<N; i++){
        if(R[i]==2){
            B[i] = 2;
        }else{
            B[i] = 0;
        }
    }
    playRound(B, R);
    int cnt = 25;
    for(int i=0; i<N; i++){
        if(R[i]>=3){
            B[i] = 3;
        }else if(B[i]!=0 && cnt>0){
            B[i] = 1;
            cnt--;
        }else B[i] = 0;
    }
    playRound(B, R);
    for(int i=0; i<N; i++){
        if(R[i]>=4){
            B[i] = 13;
        }else   B[i] = 0;
    }
    playRound(B, R);
    for(int i=0; i<N; i++){
        if(R[i]>=14){
            return i;
        }
    }
    return -1;
}

int chk(int x){
    B[0] = B[1] = x;
    playRound(B, R);
    if(R[0]>x && R[1]>x){
        return 2;
    }else if(R[0]<=x && R[1]<=x){
        return 3;
    }else{
        if(R[0]>R[1])   return 0;
        return 1;
    }
}

int greaterValue(int N, int W) {
    int t = chk(3);
    if(t==0)    return 0;
    if(t==1)    return 1;
    if(t==2){
        t = chk(5);
        if(t==0)    return 0;
        if(t==1)    return 1;
        if(t==2){
            t = chk(8);
            if(t==0)    return 0;
            return 1;
        }
    }else{
        t = chk(2);
        if(t==0)    return 0;
        if(t==1)    return 1;
        if(t==3){
            t = chk(1);
            if(t==0)    return 0;
            return 1;
        }
    }
    return -1;
}

int xx, yy;

int chk2(int k){
    B[xx] = B[yy] = k;
    playRound(B, R);
    B[xx] = B[yy] = 0;
    if(R[xx]>k && R[yy]>k){
        return 2;
    }else if(R[xx]<=k && R[yy]<=k){
        return 3;
    }else{
        if(R[xx]>R[yy])   return 0;
        return 1;
    }
}

bool sf2(int x, int y){
    xx = x; yy = y;
    int t = chk2(3);
    if(t==0)    return 0;
    if(t==1)    return 1;
    if(t==2){
        t = chk2(5);
        if(t==0)    return 0;
        if(t==1)    return 1;
        if(t==2){
            t = chk2(8);
            if(t==0)    return 0;
            return 1;
        }
    }else{
        t = chk2(2);
        if(t==0)    return 0;
        if(t==1)    return 1;
        if(t==3){
            t = chk2(1);
            if(t==0)    return 0;
            return 1;
        }
    }
    return -1;
}

int n;

bool sf(int x, int y){
    B[x] = B[y] = 100;
    playRound(B, R);
    B[x] = B[y] = 0;
    if(R[x]>R[y])   return 1;
    return 0;
}

int arr[100];
vector<int> v;

void srt(int x, int y){
    if(x==y)    return;
    int m = (x+y)/2;
    srt(x, m); srt(m+1, y);
    int i1 = x, i2 = m+1;
    while(!v.empty())   v.pop_back();
    while(i1<=m || i2<=y){
        if(i1>m){
            v.pb(arr[i2++]);
        }else if(i2>y){
            v.pb(arr[i1++]);
        }else{
            bool t = sf(arr[i1], arr[i2]);
            if(t){
                v.pb(arr[i2++]);
            }else{
                v.pb(arr[i1++]);
            }
        }
    }
    for(int i=0; i<v.size(); i++){
        arr[i+x] = v[i];
    }
    return;
}


void srt2(int x, int y){
    if(x==y)    return;
    int m = (x+y)/2;
    srt2(x, m); srt2(m+1, y);
    int i1 = x, i2 = m+1;
    while(!v.empty())   v.pop_back();
    while(i1<=m || i2<=y){
        if(i1>m){
            v.pb(arr[i2++]);
        }else if(i2>y){
            v.pb(arr[i1++]);
        }else{
            bool t = sf2(arr[i1], arr[i2]);
            if(!t){
                v.pb(arr[i2++]);
            }else{
                v.pb(arr[i1++]);
            }
        }
    }
    for(int i=0; i<v.size(); i++){
        arr[i+x] = v[i];
    }
    return;
}
void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        n = N;
        for(int i=0; i<N; i++){
            arr[i] = i;
        }
        srt(0, N-1);
        for(int i=0; i<N; i++){
            P[arr[i]] = i+1;
        }
    } else {
        n = N;
        for(int i=0; i<N; i++){
            arr[i] = i;
        }
        srt2(0, N-1);
        for(int i=0; i<N; i++){
            P[arr[i]] = i+1;
        }
    }
}

Compilation message (stderr)

koala.cpp: In function 'void srt(int, int)':
koala.cpp:176:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v.size(); i++){
                  ~^~~~~~~~~
koala.cpp: In function 'void srt2(int, int)':
koala.cpp:203:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v.size(); i++){
                  ~^~~~~~~~~

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