Submission #1211342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211342		LIA	Cave (IOI13_cave)	C++17	64 / 100	122 ms	516 KiB

cave

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
#include "cave.h"

ll s[5002];
vll pos;
vb ass;
ll n;
void update(ll i,ll endi) {
 for (;i<=endi ;i++) {
   if (!ass[i]) s[i] = (s[i]==0?1:0);
 }
}
void bl(ll i) {
  ll l = 0, r =n-1;
  ll last = 0;
  ll t = tryCombination(s);

  while (l<=r) {
    if(l==r) {
      if (last == i) {
        update(l,l);
      }
      ass[l] = 1;
      pos[l] = i;
      return;
    }
    ll mid = (r+l)/2;
    update(l,mid);
    ll t1 = tryCombination(s);
    if (t1==-1) t1 =n;
    if (t==-1) t =n;
    if ((t1==i && t>i) || (t==i && t1>i)) {
      r = mid;
    }
    else l = mid+1;
    t = t1;
    last = t1;
  }
  if (last == i) {
    update(l,l);
  }
    ass[l] = 1;
    pos[l] = i;
}
void exploreCave(int N) {
  n= N;
  pos.resize(n);
  ass.resize(n);
  memset(s, 0, sizeof(s));
  loop(i,0,n) {
  bl(i);
  }
  ll posi[n];
  loop(i,0,n) posi[i] = pos[i];
  answer(s, posi);
}

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