제출 #962696

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
962696		n3rm1n	동굴 (IOI13_cave)	C++17	100 / 100	468 ms	832 KiB

cave

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

int is_fixed[5005], gen_fixed[5005];
bool check(int n, int door, int index)
{
    int c[n];
    for (int i = 0 ; i < n ; ++ i)
        c[i] = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++ i )
    {
        if(is_fixed[i])c[i] = gen_fixed[i];
        else
        {
            cnt ++;
            if(cnt <= index)c[i] = 0;
            else c[i] = 1;
        }
    }
    int feedback = tryCombination(c);
    return (feedback > door || feedback == -1);
}
bool check2(int n, int door, int index)
{
    int c[n];
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        c[i] = 0;
    for (int i = 0; i < n; ++ i )
    {
        if(is_fixed[i])c[i] = gen_fixed[i];
        else
        {
            cnt ++;
            if(cnt <= index)c[i] = 1;
            else c[i] = 0;
        }
    }
    int feedback = tryCombination(c);
   //cout << "na " << index << " " << feedback << endl;
    return (feedback > door || feedback == -1);
}
void exploreCave(int N)
{
    int n = N;
    int s[n], feedback;
    int fixed[n]; /// opravi i gen_fixed
    int d[n];
    for (int i = 0; i < n; ++ i)
    {
        fixed[i] = 0;
        s[i] = 0;
        d[i] = 0;
    }
    for (int i = 0; i < n; ++ i)
    {
        feedback = tryCombination(s);

        if(feedback == -1 || feedback > i) /// s 0 se otvarq, vsichko 1ici pyrvata mid-nata 0 kydeto se otvarq
        {
            /// edinici
            int l = 1, r = n-i, mid, ans = 1;
            while(l <= r)
            {
                mid = (l + r)/2;
                if(check(n, i, mid))
                {
                    r = mid - 1;
                    ans = mid;
                }
                else l = mid + 1;
            }
            int cnt_non = 0;
            for (int j = 0; j < n; ++ j)
            {
                if(is_fixed[j])continue;
                cnt_non ++;
                if(cnt_non == ans)
                {
                    fixed[j] = 0;
                    gen_fixed[j] = 0;
                    is_fixed[j] = 1;
                    d[j] = i;
                    s[j] = 0;
                    //cout << i << " " << j << " " << fixed[j] << endl;
                    break;
                }
            }
        }
        else /// s 1 se otvarq, pyrvoto promeneno na 1ci kydeot stava
        {
           int l = 1, r = n-i, mid, ans = 1;
            while(l <= r)
            {
                mid = (l + r)/2;
                if(check2(n, i, mid))
                {
                    r = mid - 1;

                    ans = mid;
                }
                else l = mid + 1;
            }
            int cnt_non = 0;
            for (int j = 0; j < n; ++ j)
            {
                if(is_fixed[j])continue;
                cnt_non ++;
                if(cnt_non == ans)
                {
                    fixed[j] = 1;
                    gen_fixed[j] = 1;
                    is_fixed[j] = 1;
                    d[j] = i;
                    s[j] = 1;
                    //cout << i << " " << j << " " << fixed[j] << endl;
                    break;
                }
            }
        }
    }
    answer(fixed, d);
}

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