Submission #978080

#	Time	Username	Problem	Language	Result	Execution time	Memory
978080		salmon	Koala Game (APIO17_koala)	C++14	92 / 100	99 ms	596 KiB

koala

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

int minValue(int N, int W) {
    int res[N];
    int in[N];

    for(int i = 0; i < N; i++){
        in[i] = 0;
    }
    in[0] = 1;

    playRound(in,res);

    int p = -1;
    for(int i = 0; i < N; i++){
        if(res[i] <= in[i]){
            p = i;
        }
    }

    return p;
}

int maxValue(int N, int W) {
    set<int> sat;
    int res[N];
    int in[N];

    for(int i = 0; i < N; i++){
        sat.insert(i);
        in[i] = 0;
    }

    while(sat.size() != 1){
        int num = 100 / sat.size();

        for(int i = 0; i < N; i++){
            in[i] = 0;
        }

        for(int i : sat){
            in[i] = num;
        }

        playRound(in,res);

        for(int i = 0; i < N; i++){
            if(res[i] <= in[i] && sat.find(i) != sat.end()){
                sat.erase(i);
            }
        }
    }



    for(int i : sat) return i;
}

//9 5 3
int greaterValue(int N, int W) {
    int in[N];
    int res[N];

    int it = minValue(N, W);

    if(it == 0) return 1;
    if(it == 1) return 0;

    for(int i = 0; i < N; i++){
        in[i] = 0;
    }

    in[0] = 4;
    in[1] = 4;

    playRound(in,res);

    if(res[0] > in[0] && res[1] <= in[1]) return 0;
    if(res[1] > in[1] && res[0] <= in[0]) return 1;

    if(res[0] > in[0]){
        in[0] = 8;
        in[1] = 8;
    }
    else{
        in[0] = 2;
        in[1] = 2;
    }

    playRound(in,res);

    if(res[0] > in[0] && res[1] <= in[1]) return 0;
    if(res[1] > in[1] && res[0] <= in[0]) return 1;

    in[0] = 2;
    in[1] = 2;
}

bool b(int a, int b){
    if(b == -1) return true;
    if(a == -1) return false;

    int in[100];
    int res[100];

    for(int i = 0; i < 100; i++){
        in[i] = 0;
    }

    in[a] = 100;
    in[b] = 100;

    playRound(in,res);

    return in[b] < res[b];
}

bool c(int a, int b){
    if(b == -1) return true;
    if(a == -1) return false;

    int in[100];
    int res[100];

    for(int i = 0; i < 100; i++){
        in[i] = 0;
    }

    in[a] = 8;
    in[b] = 8;

    playRound(in,res);

    if(res[a] > in[a] && res[b] <= in[b]) return false;
    if(res[b] > in[b] && res[a] <= in[a]) return true;
}

vector<int> sblort(vector<int> input){

    queue<vector<int>> q;

    for(int i : input){
        q.push({i,-1});
    }

    while(q.size() != 1){
        vector<int> v1 = q.front();
        q.pop();
        vector<int> v2 = q.front();
        q.pop();

        vector<int> v3;

        int it1 = 0;
        int it2 = 0;
        for(int i = 0; i < v1.size() + v2.size() - 1; i++){
            if(c(v1[it1],v2[it2])){
                v3.push_back(v1[it1]);
                it1++;
            }
            else{
                v3.push_back(v2[it2]);
                it2++;
            }
        }

        q.push(v3);
    }

    q.front().pop_back();

    return q.front();
}

void allValues(int N, int W, int *P) {
    if (W == 2*N) {
        queue<vector<int>> q;
        vector<int> v;

        for(int i = 0; i < N; i++){
            vector<int> temp = {i,-1};
            q.push(temp);
        }

        while(q.size() != 1){
            vector<int> v1,v2,v3;

            v1 = q.front();
            q.pop();
            v2 = q.front();
            q.pop();

            int it1,it2;
            it1 = 0;
            it2 = 0;

            for(int i = 0; i < v1.size() + v2.size() - 1; i++){
                if(b(v1[it1],v2[it2])){
                    v3.push_back(v1[it1]);
                    it1++;
                }
                else{
                    v3.push_back(v2[it2]);
                    it2++;
                }
            }

            q.push(v3);
        }

        v = q.front();

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

    }
    else{
        int in[100];
        int res[100];
        set<int> sat;
        set<int> tempsat;
        set<int> sad;
        vector<int> input;
        vector<int> order;
        vector<int> v;

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

        playRound(in,res);

        for(int i = 0; i < N; i++){
            if(res[i] > in[i]){
                input.push_back(i);
            }
        }

        for(int i = 0; i < N; i++){
            if(res[i] <= in[i]){
                sat.insert(i);
            }
            else{
                sad.insert(i);
            }
        }

        for(int i = 0; i < 49; i++){
            in[*(sad.begin())] = 0;
            sad.erase(sad.begin());
            in[*(sad.begin())] = 0;
            sad.erase(sad.begin());

            playRound(in,res);

            for(int i = 0; i < N; i++){
                if(res[i] > in[i] && sat.find(i) != sat.end()){
                    sat.erase(i);
                    order.push_back(i);
                    sad.insert(i);
                }
            }
        }

        order.push_back(*(sat.begin()));

        reverse(order.begin(),order.end());

        for(int i = 0; i < N; i++){
            in[i] = 1;
        }

        vector<int> temp = order;
        vector<int> memp;

        sat.clear();

        for(int i : input){
            sat.insert(i);
        }

        set<pair<int,int>> psat;

        for(int i = 0; i < 9; i++){
            in[temp.back()] = 0;
            temp.pop_back();
            in[temp.back()] = 0;
            temp.pop_back();

            playRound(in,res);

            for(int i = 0; i < N; i++){
                if(res[i] <= in[i] && sat.find(i) != sat.end()){
                    sat.erase(i);
                    order.push_back(i);
                    psat.insert({order.size(),i});
                }
            }
        }

        for(int i = 0; i < 16; i++){
            in[temp.back()] = 0;
            temp.pop_back();
            in[temp.back()] = 0;
            temp.pop_back();
        }

        in[order[49]] = 1;
        psat.insert({1000,order[49]});
        vector<int> seq = {2,3,2,3,2,3,1,1};
        while(!psat.empty() && !seq.empty()){
            for(int i = 0; i < seq.back(); i++){
                in[psat.begin() -> second] = 0;
                psat.erase(psat.begin());
            }
            seq.pop_back();

            playRound(in,res);

            for(int i = 0; i < N; i++){
                if(res[i] <= in[i] && sat.find(i) != sat.end()){
                    sat.erase(i);
                    order.push_back(i);
                    psat.insert({order.size(),i});
                }
            }
        }

        input.clear();

        for(int i : sat){
            input.push_back(i);
        }

        v = sblort(input);
        input.clear();

        for(int i : v){
            order.push_back(i);
        }

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

Compilation message (stderr)

koala.cpp: In function 'std::vector<int> sblort(std::vector<int>)':
koala.cpp:158:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         for(int i = 0; i < v1.size() + v2.size() - 1; i++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:199:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |             for(int i = 0; i < v1.size() + v2.size() - 1; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:27:14: warning: control reaches end of non-void function [-Wreturn-type]
   27 |     set<int> sat;
      |              ^~~
koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:98:11: warning: control reaches end of non-void function [-Wreturn-type]
   98 |     in[1] = 2;
      |     ~~~~~~^~~
koala.cpp: In function 'bool c(int, int)':
koala.cpp:138:1: warning: control reaches end of non-void function [-Wreturn-type]
  138 | }
      | ^

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