Submission #978405

#	Time	Username	Problem	Language	Result	Execution time	Memory
978405		salmon	Koala Game (APIO17_koala)	C++14	74 / 100	85 ms	600 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();
        printf("%d\n",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();
}

vector<int> functon(vector<int> input, int num){
    int in[100], res[100];
    set<int> sat;
    vector<int> v1;

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

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

    for(int i = 1; i < 2; i++){
        playRound(in,res);

        for(int i = 0; i < 100; i++){
            if(res[i] > in[i] && sat.find(i) != sat.end()){
                v1.push_back(i);
            }
        }
    }
    //printf("%d\n",v1.size());
    return v1;
}

vector<int> functin(vector<int> input, vector<int> n, int num){
    int in[100], res[100];
    set<int> sat;
    set<int> sat1;
    vector<int> v1;

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

    for(int i : n){
        sat1.insert(i);
    }

    for(int i = 0; i < input.size(); i++){
        if(sat1.find(input[i]) != sat1.end() ) continue;
        in[input[i]] = num;
        sat.insert(input[i]);
    }

    for(int i = 1; i < 2; i++){
        playRound(in,res);

        for(int i = 0; i < 100; i++){
            if(res[i] > in[i] && sat.find(i) != sat.end()){
                v1.push_back(i);
            }
        }
    }
    //printf("%d\n",v1.size());
    return v1;
}

vector<int> functun(vector<int> input, vector<int> n, int num, int fum){
    int in[100], res[100];
    set<int> sat;
    set<int> sat1;
    vector<int> v1;

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

    for(int i : n){
        sat1.insert(i);
        in[i] = fum;
    }

    for(int i = 0; i < input.size(); i++){
        if(sat1.find(input[i]) != sat1.end() ) continue;
        in[input[i]] = num;
        sat.insert(input[i]);
    }

    for(int i = 1; i < 2; i++){
        playRound(in,res);

        for(int i = 0; i < 100; i++){
            if(res[i] > in[i] && sat.find(i) != sat.end()){
                v1.push_back(i);
            }
        }
    }
    //printf("%d\n",v1.size());
    return v1;
}

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;
        vector<int> v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12,v13,v14,v15,v16,v17,v18,v19,v20,v21,v22,v23,v24,v25,v26,v27,v28,v29,v30,v31,v32,v33;
        vector<vector<int>> vl;
        vector<vector<int>> vv;

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

        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] = 0;
        }

        //printf("%d\n",input.size());


        v1 = functon(input, 2);
        v2 = functon(v1, 4);
        //printf("v2 %d\n",v2.size());
        v3 = functon(v2, 11);

        vl.push_back(v3);

        for(int i = 0; i < 8; i++){
            vector<int> temp = functin(v2, vl.back(), 10);
            temp.insert(temp.end(), vl.back().begin(), vl.back().end());
            vl.push_back(temp);
        }

        sat.clear();
        int cont = 100;
        for(vector<int> v : vl){
            for(int i : v){
                if(sat.find(i) == sat.end()){
                    P[i] = cont;
                    cont--;
                    sat.insert(i);
                }
            }
        }
        //10 done

        vl.push_back(v2);
        for(int i = 0; i < 1; i++){
            vector<int> temp = functun(v1, vl.back(), 4, 3);
            temp.insert(temp.end(), vl.back().begin(), vl.back().end());
            vl.push_back(temp);
        }
        /*for(int i = 0; i < 1; i++){
            printf("s");
            vector<int> temp = functun(v1, vl.back(), 5, 1);
            temp.insert(temp.end(), vl.back().begin(), vl.back().end());
            vl.push_back(temp);
        }*/



        //input.clear();

        /*for(int i : sat){
            input.push_back(i);
            printf("s");
        }*/
        vector<int> temp;
        for(int i : input){
            if(sat.find(i) == sat.end()) temp.push_back(i);
        }

        input = temp;

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

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

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

Compilation message (stderr)

koala.cpp: In function 'int maxValue(int, int)':
koala.cpp:38:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   38 |         printf("%d\n",sat.size());
      |                 ~^    ~~~~~~~~~~
      |                  |            |
      |                  int          std::set<int>::size_type {aka long unsigned int}
      |                 %ld
koala.cpp: In function 'std::vector<int> sblort(std::vector<int>)':
koala.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         for(int i = 0; i < v1.size() + v2.size() - 1; i++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp: In function 'std::vector<int> functon(std::vector<int>, int)':
koala.cpp:187:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for(int i = 0; i < input.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
koala.cpp: In function 'std::vector<int> functin(std::vector<int>, std::vector<int>, int)':
koala.cpp:219:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |     for(int i = 0; i < input.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
koala.cpp: In function 'std::vector<int> functun(std::vector<int>, std::vector<int>, int, int)':
koala.cpp:253:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  253 |     for(int i = 0; i < input.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
koala.cpp: In function 'void allValues(int, int, int*)':
koala.cpp:294:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  294 |             for(int i = 0; i < v1.size() + v2.size() - 1; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:442:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  442 |         for(int i = 0; i < order.size(); 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:99:11: warning: control reaches end of non-void function [-Wreturn-type]
   99 |     in[1] = 2;
      |     ~~~~~~^~~
koala.cpp: In function 'bool c(int, int)':
koala.cpp:139:1: warning: control reaches end of non-void function [-Wreturn-type]
  139 | }
      | ^

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