제출 #237749

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237749		nicolaalexandra	동굴 (IOI13_cave)	C++14	0 / 100	241 ms	512 KiB

cave

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

int n,i,j,ans;
int v[DIM],sol[DIM],f[DIM],w[DIM];

/*void answer(int s[], int d[]){
    for (int i=0;i<n;i++)
        cout<<s[i]<<" ";
    cout<<"\n";
    for (int i=0;i<n;i++)
        cout<<d[i]<<"\n";
}

int tryCombination (int S[]){
    int ans,i;
    for (i=0;i<n;i++)
        cout<<S[i]<<" ";
    cout<<endl;
    cin>>ans;
    cout<<endl;
    return ans;
}
*/

int verif (int x, int y){
    for (int i=0;i<n;i++){
        if (f[i]){
            w[i] = v[i];
            continue;
        }
        if (i >= x && i <= y)
            w[i] = 1;
        else w[i] = 0;
    }
    return tryCombination(w);
}

void exploreCave (int N){

    n = N;
    int ok = 0;
    for (i=0;i<n;i++){
        int ans = tryCombination(v);
        if (ans == i){

            int st = 0, dr = n-1;
            while (st < dr){
                int mid = (st+dr)>>1;
                int ans = verif(st,mid);
                if (ans == -1){
                    ok = 1;
                    for (j=0;j<n;j++)
                        v[j] = w[j];
                    break;
                }
                if (ans > i)
                    dr = mid;
                else st = mid+1;
            }
            if (ok)
                break;
            /// st
            sol[st] = i;
            f[st] = 1;
            v[st] = 1;

        } else {
            /// usa i e deschisa, trb sa i gasesc perechea
            int st = 0, dr = n-1;
            while (st < dr){
                int mid = (st+dr)>>1;
                int ans = verif(st,mid);
                if (ans == -1){
                    ok = 1;
                    for (j=0;j<n;j++)
                        v[j] = w[j];
                    break;
                }
                if (ans > i)
                    dr = mid;
                else st = mid+1;
            }
            if (ok)
                break;
            sol[st] = i;
            f[st] = 1;
            v[st] = 0;
        }

    }

    for (i=0;i<n;i++){
        if (f[i])
            continue;

        if (v[i] == 0){
            v[i] = 1;
            sol[i] = tryCombination(v);
            v[i] = 0;
        } else {
            v[i] = 0;
            sol[i] = tryCombination(v);
            v[i] = 1;
        }
    }

    answer(v,sol);
}

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