Submission #817893

#	Time	Username	Problem	Language	Result	Execution time	Memory
817893		ALeonidou	Cave (IOI13_cave)	C++17	64 / 100	167 ms	440 KiB

cave

#include "cave.h"
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <string>
#include <fstream>
#include <cstring>
#include <cassert>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

#define ll int
#define llu unsigned long long
#define ld long double
#define F first
#define S second
#define endl "\n"
#define MID ((l+r)/2)

#define sorv(a) sort(a.begin(),a.end())
#define revv(a) reverse(a.begin(),a.end())
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define ins insert
#define pb push_back

#define inf 1e9
#define INF 1e18
#define MOD 1000000007
#define MOD2 998244353

typedef pair <ll, ll> ii;
typedef pair <ll,ii> iii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <iii> viii;
typedef set <ll> si;
typedef map <ll,ll> mi;

#ifndef ONLINE_JUDGE
  //#define ONLINE_JUDGE
#endif

#ifndef ONLINE_JUDGE 
  template<typename T>void printArr(T *arr,ll l,ll m=0){if(m==1){for(ll i=0;i<l;i++)cout<<arr[i]<<" ";cout<<endl;}else{cout<<endl;for(ll i=0;i<l;i++)cout<<i<<": "<<arr[i]<<endl;}}
  #define printArr2D(arr,n,m)cout<<endl;for(ll i=0;i<n;i++){for(ll j=0;j<m;j++)cout<<arr[i][j]<<" ";cout<<endl;}cout<<endl;
  template<typename T>void printVct(vector<T> v,ll m=0){if(m==1){for(ll i=0;i<sz(v);i++)cout<<v[i]<<" ";cout<<endl;}else{cout<<endl;for(ll i=0; i<sz(v);i++)cout<<i<<": "<<v[i]<<endl;}}
  template<typename T>void printVct2D(vector<vector<T> >v){cout<<endl;for(ll i=0;i<sz(v);i++){cout<<i<<": ";for(ll j=0;j<sz(v[i]);j++)cout<<v[i][j]<<" ";cout<<endl;}}
  template<typename T>void printVctPair(vector<T> v,ll m=0){if(m==1){for(ll i=0;i<sz(v);i++)cout<<v[i].F<<":"<<v[i].S<<" ";cout<<endl;}else{cout<<endl;for(ll i=0;i<sz(v);i++)cout<<i<<":  "<<v[i].F<<" : "<<v[i].S<<endl;}}
  template<typename T>void printVctPair2D(vector<vector<T> >v){cout<<endl;for(ll i=0;i<sz(v);i++){cout<<i<<": ";for(ll j=0;j<sz(v[i]);j++)cout<<v[i][j].F<<":"<<v[i][j].S<<" ";cout<<endl;}}
  template<typename T>void printVctPair3(vector<T> v,ll m=0){cout<<endl;for(ll i=0;i<sz(v);i++)cout<<i<<": ("<<v[i].F<<" : "<<v[i].S.F<<" : "<<v[i].S.S<<")"<<endl;}
  template<typename T1,typename T2>void printMap(map<T1,T2>mp){cout<<endl;for(typename map<T1,T2>::iterator it=mp.begin();it!=mp.end();it++)cout<<it->F<<" -> "<<it->S<<endl;}
  template<typename T>void printSet(set<T>st,ll m=0){typename set<T>::iterator it;if(m){for(it=st.begin();it!=st.end();it++)cout<<*it<<" ";cout<<endl;}else{cout<<endl;for(it=st.begin();it!=st.end();it++)cout<<*it<<endl;}}
  void check(ll n){cout<<"CHECKPOINT "<<n<<"\n\n";}
  #define dbg(x) cout<<#x<<":"<<x<<endl
  #define dbg2(x,y) cout<<#x<<":"<<x<<"  "<<#y<<":"<<y<<endl
  #define dbg3(x,y,z) cout<<#x<<":"<<x<<"  "<<#y<<":"<<y<<"  "<<#z<<":"<<z<<endl
  #define dbg4(x,y,z,w) cout<<#x<<":"<<x<<"  "<<#y<<":"<<y<<"  "<<#z<<":"<<z<<"  "<<#w<<":"<<w<<endl
  #define dbg5(x,y,z,w,v) cout<<#x<<":"<<x<<"  "<<#y<<":"<<y<<"  "<<#z<<":"<<z<<"  "<<#w<<":"<<w<<"  "<<#v<<":"<<v<<endl
  #define dbg6(x,y,z,w,v,u) cout<<#x<<":"<<x<<"  "<<#y<<":"<<y<<"  "<<#z<<":"<<z<<"  "<<#w<<":"<<w<<"  "<<#v<<":"<<v<<"  "<<#u<<":"<<u<<endl
  #define dbgp(x) cout<<#x<<":("<<x.F<<" "<<x.S<<")"<<endl
  #define dbgp2(x,y) cout<<#x<<":("<<x.F<<","<<x.S<<")  "<<#y<<":("<<y.F<<","<<y.S<<")"<<endl
  #define dbgt(x) cout<<#x<<":("<<x.F<<" "<<x.S.F<<" "<<x.S.S<<")"<<endl
  #define dbgt2(x,y) cout<<#x<<":("<<x.F<<" "<<x.S.F<<" "<<x.S.S<<")  "<<#y<<":("<<y.F<<" "<<y.S.F<<" "<<y.S.S<<")"<<endl
#else
  template<typename T>void printArr(T *arr,ll l,ll m=0){}
  #define printArr2D(arr,n,m)
  template<typename T>void printVct(vector<T> v,ll m=0){}
  template<typename T>void printVct2D(vector<vector<T> >v){}
  template<typename T>void printVctPair(vector<T> v,ll m=0){}
  template<typename T>void printVctPair2D(vector<vector<T> >v){}
  template<typename T>void printVctPair3(vector<T> v,ll m=0){}
  template<typename T1,typename T2>void printMap(map<T1,T2>mp){}
  template<typename T>void printSet(set<T>st,ll m=0){}
  void check(ll n){}
  #define dbg(x)
  #define dbg2(x,y)
  #define dbg3(x,y,z)
  #define dbg4(x,y,z,w)
  #define dbg5(x,y,z,w,v)
  #define dbg6(x,y,z,w,v,u)
  #define dbgp(x)
  #define dbgp2(x,y)
  #define dbgt(x)
  #define dbgt2(x,y)
#endif

const ll dx[8]={1,-1,0,0,1,1,-1,-1}, dy[8]={0,0,1,-1,1,-1,1,-1};

ll charToIntNum(char c){return (ll)c-48;} 
char intToCharNum(ll n){return (char)n+48;}
ll charToIntLower(char c){return (ll)c-97;}
char intToCharLower(ll n){return (char)n+97;}
ll charToIntUpper(char c){return (ll)c-65;}
char intToCharUpper(ll n){return (char)n+65;}

void tabb(ll n){for(ll i=0;i<n;i++)cout<<"\t";}
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);}
void yesno(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}


void exploreCave(ll n) {  
    ll tmp[n], s[n], d[n];

    //part 1: find correct switch configuration in O(nlogn)

    //init
    //loop
        //bs
            //build (keeping locked unchaned)
            //check
        //lock

    for (ll i=0; i<n; i++)
        s[i] = -1;
    for (ll i=0; i<n; i++)
        d[i] = -1;

    // cout<<"s: "; printArr(s,n,1);
    // cout<<"d: "; printArr(d,n,1);

    ll prev,cur;
    for (ll i=1; i<=n; i++){
        //dbg(i);
        for (ll j= 0; j<n; j++){
            if (s[j] == -1){
                tmp[j] = 0;
            }
            else{
                tmp[j] = s[j];
            }
        }

        // cout<<"tmp: ";
        // printArr(tmp,n,1);

        prev = min(tryCombination(tmp), i);
        if (prev == -1) prev = i;

        ll l = 0, r = n-1, mid;
        while (l < r){
            // cout<<endl;
            mid = MID;

            //build
            for (ll j = l; j<=mid; j++){
                if (s[j] == -1){
                    tmp[j] = !tmp[j];
                }
            }

            // dbg3(l,r,mid);
            // cout<<"tmp: ";
            // printArr(tmp,n,1);

            //check
            cur = min(tryCombination(tmp), i);
            if (cur == -1) cur = i;

            if (prev == cur){
                //right
                l = mid+1;
            }
            else{
                //left
                r = mid;
            }

            // dbg2(prev, cur);

            prev = cur;
        }

        if (cur == i) s[l] = tmp[l];
        else s[l] = !tmp[l];
        d[l] = i-1;

        // cout<<"s: "; printArr(s,n,1);
        // cout<<"d: "; printArr(d,n,1);
        // cout<<endl<<endl<<endl;
    }

    // cout<<endl<<endl;

    answer(s,d);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:183:9: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
  183 |         if (cur == i) s[l] = tmp[l];
      |         ^~

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