Submission #1062136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062136		andrei_iorgulescu	Cave (IOI13_cave)	C++14	100 / 100	493 ms	976 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#warning That's not FB, that's my FB

using namespace std;

int query(vector<int> x)
{
    int xx[5005];
    for (int i = 0; i < x.size(); i++)
        xx[i] = x[i];
    int vll = tryCombination(xx);
    return vll;
}

void exploreCave(int N)
{
    vector<int> s(N); /// s[i] = switch-ul pentru usa i
    vector<int> how(N); /// cum trebuie sa fie s[i] ca sa fie usa i deschisa
    for (int i = 0; i < N; i++)
    {
        vector<int> cur(N);
        for (int j = 0; j < i; j++)
            cur[s[j]] = how[j];
        vector<bool> isoc(N);
        vector<int> free_pz;
        for (int j = 0; j < i; j++)
            isoc[s[j]] = true;
        for (int j = 0; j < N; j++)
            if (!isoc[j])
                free_pz.push_back(j);
        for (auto it : free_pz)
            cur[it] = 0;
        int state0 = query(cur);
        bool s0;
        if (state0 == i)
            s0 = false;
        else
            s0 = true;
        how[i] = 1 - (int)s0;
        //cout << i << ' ' << state0 << ' ' << how[i] << endl;
        int st = -1, pas = 1 << 12;
        while (pas != 0)
        {
            if (st + pas < free_pz.size())
            {
                vector<int> recur(N);
                for (int j = 0; j < i; j++)
                    recur[s[j]] = how[j];
                for (int j = 0; j <= st + pas; j++)
                    recur[free_pz[j]] = 1;
                for (int j = st + pas + 1; j < free_pz.size(); j++)
                    recur[free_pz[j]] = 0;
                int state1 = query(recur);
                //cout << st + pas << ' ' << state1 << endl;
                bool s1;
                if (state1 == i)
                    s1 = false;
                else
                    s1 = true;
                if (s0 == s1)
                    st += pas;
            }
            pas /= 2;
        }
        st++;
        s[i] = free_pz[st];
    }
    vector<int> ans_how(N), ans_s(N);
    for (int i = 0; i < N; i++)
        ans_how[s[i]] = how[i];
    for (int i = 0; i < N; i++)
        ans_s[s[i]] = i;
    int bruh_ans_how[5005], bruh_ans_s[5005];
    for (int i = 0; i < N; i++)
        bruh_ans_how[i] = ans_how[i], bruh_ans_s[i] = ans_s[i];
    answer(bruh_ans_how, bruh_ans_s);
}

Compilation message (stderr)

cave.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
cave.cpp: In function 'int query(std::vector<int>)':
cave.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < x.size(); i++)
      |                     ~~^~~~~~~~~~
cave.cpp: In function 'void exploreCave(int)':
cave.cpp:45:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             if (st + pas < free_pz.size())
      |                 ~~~~~~~~~^~~~~~~~~~~~~~~~
cave.cpp:52:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |                 for (int j = st + pas + 1; j < free_pz.size(); j++)
      |                                            ~~^~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24