Submission #1086944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086944		MateiKing80	Cave (IOI13_cave)	C++14	12 / 100	570 ms	872 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
#define fr first
#define sc second

vector<int> ss, dd;
int n;
/*
void init()
{
    cin >> n;
    ss.resize(n);
    dd.resize(n);
    for(int i = 0; i < n; i ++)
        cin >> ss[i];
    for(int i = 0; i < n; i ++)
        cin >> dd[i];
}

void answer(vector<int> s, vector<int> d)
{
    bool ok = true;
    for(int i = 0; i < n; i ++)
        if(s[i] != ss[i] || d[i] != dd[i])
            ok = false;
    cout << (int)ok << '\n';
    for(auto i : s)
        cout << i << " ";
    cout << '\n';
    for(auto i : d)
        cout << i << " ";
    cout << '\n';
}

int tryCombination(vector<int> s)
{
    //cout << "get in there\n";
    vector<int> bn(n);
    int minn = 2e5;
    for(int i = 0; i < n; i ++)
        if(s[i] != ss[i])
            minn = min(minn, dd[i]);
    if(minn == 2e5)
        return -1;
    return minn;
}
*/
int ntc(vector<int> v)
{
    //return tryCombination(v);
    int mad[5000], sus = 0;
    for(auto i : v)
        mad[sus ++] = i;
    return tryCombination(mad);
}

void nan(vector<int> v, vector<int> w)
{
    //answer(v, w);
    int mad[5000], sus = 0;
    for(auto i : v)
        mad[sus ++] = i;
    sus = 0;
    int ultra[5000];
    for(auto i : w)
        ultra[sus ++] = i;
    answer(mad, ultra);
}

void exploreCave(int N)
{
    //init();
    n = N;
    const int lg = (int)log2(n);
    vector<pii> ans;
    vector<bool> f(n, false);
    for(int i = 0; i < n; i ++)
    {
        vector<int> sus;
        for(int j = 0; j < n; j ++)
            sus.push_back(1);
        for(auto j : ans)
            sus[j.fr] = j.sc;
        /*for(auto j : sus)
            cout << j << " ";
        cout << '\n';
        //int x;
        cout << ntc(sus) << '\n';
        cout << ntc(sus) << '\n';
        cout << ntc(sus) << '\n';
        cout << ntc(sus) << '\n';
        cout << ntc(sus) << '\n';
        cout << ntc(sus) << '\n';*/
        int x = ntc(sus);
        //cout << x;// << " " << i << '\n';
        bool turip;
        if(x == i)
            turip = 1;
        else
            turip = 0;
        //cout << "Crash afterwards\n";
        int pas = 1 << lg, pos = -1;
        while(pas)
        {
            //cout << "Morb?\n";
            vector<int> di(n, 1);
            for(int j = 0; j <= min(n - 1, pos + pas); j ++)
                di[j] = 0;
            for(auto j : ans)
                di[j.fr] = j.sc;
            bool nturip = (ntc(di) == i);
            if(nturip == turip)
                pos += pas;
            pas /= 2;
        }
        pos ++;
        //cout << pos << '\n';
        if(turip)
            ans.push_back({pos, 0});
        else
            ans.push_back({pos, 1});
    }
    vector<int> s(n), d(n);
    int sus = 0;
    for(auto i : ans)
        s[i.fr] = i.sc, d[sus ++] = i.fr;
    nan(s, d);
}

/*
4
0 0 1 0
3 1 0 2
*/

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