Submission #257259

#	Time	Username	Problem	Language	Result	Execution time	Memory
257259		Ccucumber12	Cave (IOI13_cave)	C++14	0 / 100	255 ms	504 KiB

cave

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <cstring>
#include <string.h>
#include <sstream>
#include <iomanip>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <tuple>
#include <vector>
#include <random>
#include <chrono>
#include <stdio.h>
#include <stdlib.h>
#include "cave.h"
using namespace std;

#define F first
#define S second
#define siz(v) ((int)v.size())
#define rs(n) resize(n)
#define ALL(v) v.begin(),v.end()
#define reset(v) memset((v),0,sizeof(v))
#define EB emplace_back
#define MP make_pair
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define debug(x) cout << " > " << #x << ':' << x << endl;
#define kiyohime ios::sync_with_stdio(false);cin.tie(0);
#define endl '\n'

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using vec = vector<T>;
template<typename T> using Prior = priority_queue<T>;
template<typename T> using prior = priority_queue<T, vec<T>, greater<T>>;

const int INF = 1e9;
const ll LLINF = (ll)4*1e18;
const ll MOD = 1e9+7;
const double PI  = 3.14159265358;
const double EPS = 1e-8;
const int xx[8] = {0,1,0,-1,1,1,-1,-1};
const int yy[8] = {1,0,-1,0,1,-1,-1,1};

void pmod(ll &a, ll b) {a = (a+b)%MOD;}
void mmod(ll &a, ll b) {a = (a-b+MOD)%MOD;}
void tmod(ll &a, ll b) {a = (a*b)%MOD;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll POW(ll a, ll b) {ll res=1; do{if(b%2)tmod(res,a);tmod(a,a);}while(b>>=1); return res;}
template<typename T> void amax(T &a, T b) {if(a < b) a = b;}
template<typename T> void amin(T &a, T b) {if(a > b) a = b;}

#define N 5010
//
//int pos[N], ans[N], dt[N];
//int n;
//
//int tryCombination(int a[]){
//    rep(i, n) if(a[dt[i]] != ans[dt[i]]) return i;
//    return -1;
//}
//
//void answer(int a[], int b[]){
//    rep(i, n)
//        cout << pos[i] << " \n"[i == n-1];
//    rep(i, n)
//        cout << a[i] << " \n"[i == n-1];
//    cout << endl;
//
//    rep(i, n)
//        cout << ans[i] << " \n"[i == n-1];
//    rep(i, n)
//        cout << b[i] << " \n"[i == n-1];
//    cout << endl;
//}

void exploreCave(int n){
    int pos[n], ans[n], l, r, tmp;
    bool cur, vis[n];
    
    rep(i, n) pos[i] = ans[i] = vis[i] = 0;
    
    rep(i, n){
        tmp = tryCombination(ans);
        
        cur = (tmp > i || tmp == -1);
        l = 0;
        r = n;
        
        while(r - l > 1){
            int mid = (r + l) >> 1;
            
            REP(j, l, mid-1)
                if(!vis[j]) ans[j] = 1;
            
            tmp = tryCombination(ans);
            
            REP(j, l, mid-1)
                if(!vis[j]) ans[j] = 0;
            
            if(cur != (tmp > i || tmp == -1)) r = mid;
            else                              l = mid;
        }
        
        pos[l] = i;
        ans[l] = !cur;
        vis[l] = true;
    }
    
    answer(pos, ans);
}

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