Submission #545516

#	Time	Username	Problem	Language	Result	Execution time	Memory
545516		MohamedAliSaidane	Cave (IOI13_cave)	C++14	100 / 100	294 ms	460 KiB

cave

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

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

#define pb push_back
#define popb pop_back
#define pf push_front
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second

int nx[4] = {0,0,1,-1}, ny[4] = {1,-1,0,0};
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}

/*int N;
vi S, D, C;
void answer(vi A, vi B)
{
    for(int i = 0; i < N; i ++)
        cout << A[i] << ' ';
    cout << '\n';
    for(int i = 0; i < N; i ++)
        cout << B[i] << ' ';
}
int tryCombination(vi A)
{
    for(int door = 0; door < N;door ++)
    {
        if(A[C[door]] != S[C[door]])
            return door;
    }

    return -1;
}*/
void exploreCave(int n)
{
    int ans[n], st[n];
    int cur[n]; memset(cur,0,sizeof(cur));
    bool vis[n]; memset(vis,false,sizeof(vis));
    for(int door = 0; door < n; door ++)
    {
        int repp = tryCombination(cur);
        if(repp == -1 || repp > door)
        {
            int debut = 0;
            int fin = n - 1;
            while(debut < fin)
            {
                int mid = (debut+fin)/2;
                for(int i = debut; i <= mid; i ++)
                {
                    if(vis[i])
                        continue;
                    cur[i] = 1;
                }
                int rep = tryCombination(cur);
                for(int i = debut; i <= mid; i ++)
                {
                    if(vis[i])
                        continue;
                    cur[i] = 0;
                }
                if(rep == door)
                {
                    fin = mid;
                }
                else
                    debut = mid + 1;

            }
            ans[debut] = door;
            st[fin] = cur[fin] = 0;
            vis[fin] = 1;

        }
        else
        {
            int debut = 0;
            int fin = n - 1;
            while(debut < fin)
            {
                int mid = (debut+fin)/2;
                for(int i = debut; i <= mid; i ++)
                {
                    if(vis[i])
                        continue;
                    cur[i] = 1;
                }
                int rep = tryCombination(cur);
                for(int i = debut; i <= mid; i ++)
                {
                    if(vis[i])
                        continue;
                    cur[i] = 0;
                }
                if(rep > door || rep == -1)
                {
                    fin = mid;
                }
                else
                    debut = mid + 1;

            }
            ans[debut] = door;
            st[fin] = cur[fin] = 1;
            vis[fin] = 1;

        }
    }
    answer(st,ans);
}/*
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N;
    S.assign(N,0); D.assign(N,0);
    C.assign(N,0);
    for(int i = 0; i < N; i ++)
        cin >> S[i];
    for(int i = 0; i < N; i ++)
        cin >> D[i];
    for(int i = 0; i < N; i ++)
        C[D[i]] = i;
    exploreCave(N);

}
*/

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