이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "cave.h"
#define MAX_N 5000
using namespace std;
int tryCombination(int S[]);
void answer(int S[], int D[]);
int id[MAX_N + 1];
int v[MAX_N + 1];
const int UNDEF = -1;
int q[MAX_N + 1];
void baga(int st, int dr, int val)
{
for(int i = st; i <= dr; i ++)
{
//cout << " BAGAM " << i << " " << val << "\n";
//cout << " AVEM " << v[i] << " == " << UNDEF << " " << (v[i] == UNDEF) << "\n";
q[i] = (v[i] == UNDEF ? val : v[i]);
}
}
int tmp[MAX_N + 1];
int n;
void copyV(int a[], int b[])
{
for(int i = 0; i < n; i ++)
a[i] = b[i];
}
void doSpec()
{
for(int i = 0; i < n; i ++)
{
q[i] = 1 - q[i];
int x = tryCombination(q);
id[i] = x;
v[i] = 1 - q[i];
q[i] = 1 - q[i];
}
answer(v, id);
}
int done[MAX_N + 1];
int CATE = 0;
void divide(int st, int dr, int idx, int val)
{
// cout << " INTRA " << st << " " << dr << " " << idx << " " << val << "\n";
if(st == dr)
{
// cout << " PE POZ " << st << " ARE VAL " << val << " SI ID " << idx << "\n";
id[st] = idx;
v[st] = val;
q[st] = val;
done[idx] = 1;
CATE ++;
return;
}
/* cout << idx << " ESTE " << done[idx] << "\n";
for(int i = 0; i < n; i ++)
cout << v[i] << " ";
cout << "\n";
for(int i =0 ; i < n; i++)
cout << id[i] << " ";
cout << "\n";*/
int tmp[MAX_N + 1];
int mid = (st + dr) >> 1;
while(done[idx] == 0)
{/*
cout << " SUNITEM " << st << " " << dr << " " << idx << " " << val << "\n";
for(int i =0; i <= 5; i ++)
cout << q[i ] << " " ;
cout << "\n";*/
copyV(tmp, q);
baga(st, mid, val);
/*
for(int i =0; i <= 5; i ++)
cout << q[i ] << " " ;
cout << "\n";*/
int x = tryCombination(q);
// cout << "PR ++ " << x << "\n";
/* for(int i =0 ; i < n; i++)
cout << q[i] << " ";
cout << "\n";*/
if(x == -1)
doSpec();
if(x < idx)
{
divide(st, mid, x, 1 - val);
copyV(q, tmp);
}
else
if(x == idx)
{
divide(mid + 1, dr, idx, val);
copyV(q, tmp);
}
else
if(x > idx)
{
copyV(q, tmp);
divide(st, mid, idx, val);
}
}
}
void exploreCave(int N)
{
n = N;
for(int i = 0; i < N; i ++)
{
v[i] = UNDEF;
id[i] = UNDEF;
q[i] = 0;
}
while(CATE < N)
{
baga(0, N, 0);
int x = tryCombination(q);
// cout << " PRIMA E " << x << " " << "\n";
if(x == -1)
doSpec();
divide(0, N, x, 1);
}
answer(v, id);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |