Submission #978681

#	Time	Username	Problem	Language	Result	Execution time	Memory
978681		WongYiKai	Koala Game (APIO17_koala)	C++14	85 / 100	92 ms	724 KiB

koala

#include "koala.h"
#include <bits/stdc++.h>
using namespace std;
 
int minValue(int N, int W) {
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    int b[N],r[N];
    for (int i=0;i<N;i++){
        b[i] = 0;
    }
    b[0] = 1;
    playRound(b,r);
    for (int i=0;i<100;i++){
        if (r[i]==0) return i;
    }
    return 0;
}
 
int maxValue(int N, int W) {
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    int b[N],r[N];
    for (int i=0;i<N;i++){
        b[i] = 1;
    }
    //b[0] = 1;
    playRound(b,r);
    queue<int> next;
    for (int i=0;i<N;i++){
        if (r[i]==2) next.push(i);
    }
    for (int i=0;i<N;i++){
        b[i] = 0;
    }
    while (!next.empty()) {
        b[next.front()]=2;
        next.pop();
    }
    playRound(b,r);
    for (int i=0;i<N;i++){
        if (r[i]==3) next.push(i);
    }
    for (int i=0;i<N;i++){
        b[i] = 0;
    }
    while (!next.empty()) {
        b[next.front()]=4;
        next.pop();
    }
    playRound(b,r);
    for (int i=0;i<N;i++){
        if (r[i]==5) next.push(i);
    }
    for (int i=0;i<N;i++){
        b[i] = 0;
    }
    while (!next.empty()) {
        b[next.front()]=11;
        next.pop();
    }
    playRound(b,r);
    for (int i=0;i<N;i++){
        if (r[i]==12) return i;
    }
    return 0;
}
 
int compare(int a, int bb){
	int N=100;
	int b[N],r[N];
    for (int i=0;i<N;i++){
        b[i] = 1;
    }
    //b[0] = 1;
    playRound(b,r);
    queue<int> next;
    int grp[100];
    vector<int> grps[5];
    for (int i=0;i<N;i++){
        if (r[i]==2) next.push(i);
        if (r[i]==2){
			grp[i]=3;
		}
		else grp[i]=1;
    }
    for (int i=0;i<N;i++){
        b[i] = 0;
    }
    while (!next.empty()) {
        b[next.front()]=2;
        next.pop();
    }
    playRound(b,r);
    for (int i=0;i<N;i++){
        if (r[i]==3) next.push(i);
        if (r[i]==3) grp[i] = 4;
        else if (r[i]==1) grp[i] = 2;
    }
    for (int i=0;i<N;i++){
		grps[grp[i]].push_back(i);
	}
	
	if (grp[a]>grp[bb]) return a;
	else if (grp[a]<grp[bb]) return bb;
	
    for (int i=0;i<N;i++){
        b[i] = 0;
    }
	if (grp[a]==2){
		b[a]=6;
		b[bb]=6;
	}
	else if (grp[a]==3){
		b[a]=8;
		b[bb]=8;
	}
	else if (grp[a]==4){
		b[a]=10;
		b[bb]=10;
	}
	else{
		for (int i=0;i<N;i++){
			b[i] = 1;
		}
		b[a]=0;
		b[bb]=0;
		b[grps[4][0]]=0;
	}
	
	playRound(b,r);
	if (r[a]!=0) return a;
	else return bb;
}
	
 
int greaterValue(int N, int W) {
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    return compare(0,1);
}

void all1(int *P){
    int b[100],r[100],a[100];
    for (int i=0;i<100;i++) a[i] = i;
    stable_sort(a,a+100,[&](int aa,int bb){
        memset(b,0,sizeof(b));
        b[aa]=100;
        b[bb]=100;
        playRound(b,r);
        if (r[aa]==0) return true;
        return false;
    });

    for (int i=0;i<100;i++){
        P[a[i]]=i+1;
    }
}

void all2(int *P, int s, int e, vector<int> next){
    if (next.size()==1) {
        P[next[0]]=s;
        return;
    }
    int b[100],r[100];
    memset(b,0,sizeof(b));
    for (int i=1;i<=100;i++){
        for (auto item:next){
            b[item]=i;
        }
        playRound(b,r);
        vector<int> left,right;
        for (auto item:next){
            if (r[item]==0) left.push_back(item);
            else right.push_back(item);
        }
        // cout << "left: ";
        // for (auto item:left) cout << item << " ";
        // cout << "\nright: ";
        // for (auto item:right) cout << item << " ";
        // cout << "\n";
        if (left.empty()||right.empty()) continue;
        all2(P,s,left.size()+s-1,left);
        all2(P,left.size()+s,e,right);
        return;
    }

}
 
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.
        all1(P);
    } else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        vector<int> next;
        for (int i=0;i<100;i++) next.push_back(i);
        all2(P,1,N,next);
    }
}

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