Submission #461186

#	Time	Username	Problem	Language	Result	Execution time	Memory
461186		mtxas	Cave (IOI13_cave)	C++14	100 / 100	349 ms	532 KiB

cave

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <deque>
#include <cstring>
#include <math.h>
#include <iomanip>
#include <unordered_map>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <cave.h>
/****************************************************************************
								MACROS
****************************************************************************/
#define ll long long
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define _for(a, b, c) for(int (a) = (b); (a) < (c); ++(a))
#define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); ++(a))
#define _forn(a, b, c) for(int (a) = (b); (a) > (c); (a)--)
#define _forneq(a, b, c) for(int (a) = (b); (a) >= (c); (a)--)
#define turbo() cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define _fre() freopen("input.txt", "r", stdin)
#define sz(x) ((int)x.size())
#define all(a) a.begin(), a.end()
#define PI 3.141592654
#define mem(x, val) memset(x, val, sizeof(x))
#define pii pair<int, int>
#define mii map<int, int>
using namespace std;
/****************************************************************************
							STRUCTS
****************************************************************************/
/****************************************************************************
							VARIABLES
****************************************************************************/
const int maxn =5e3;
bool old[maxn];
int S[maxn], D[maxn];
int n;
/****************************************************************************
							FUNCTIONS
****************************************************************************/

/****************************************************************************
								MAIN
****************************************************************************/
/*int tryCombination(int X[]){
    _for(i, 0, n) cout<<S[i]<<" "; cout<<'\n';
    cout<<"Enter answer: "; int ans; cin>>ans;
    return ans;
}
void answer(int A[], int B[]){
    cout<<"D: "; _for(i, 0, n) cout<<D[i]<<" ";
}*/
void keisk(int l, int r){
    _foreq(i, l, r) if(!old[i]) S[i] = !S[i];
}
void exploreCave(int N){
    n = N;
    _for(j, 0, n){ // randam, kuris kontroliuoja j-tasias duris
        int _res = tryCombination(S); if(_res == -1) _res = n;
        bool wasOpen = _res > j;
        int L = 0, R = N-1, k = (L+R)/2;
        while(L<R){
            keisk(L, k); int res = tryCombination(S);
            if(res == -1) res = n;
            bool isOpen = res > j; keisk(L, k);
            if(isOpen != wasOpen) R = k;
            else L = k+1;
            k = (L+R)/2;
        }
        D[k] = j;
       // cout<<"jungiklis "<<k<<" kontroliuoja "<<j<<"-asias duris\n";
        if(!wasOpen) keisk(k, k); old[k] = 1;
    }
    answer(S, D);
}
/*int main(){
    exploreCave(4);
}*/

Compilation message (stderr)

cave.cpp: In function 'void keisk(int, int)':
cave.cpp:26:33: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   26 | #define _foreq(a, b, c) for(int (a) = (b); (a) <= (c); ++(a))
      |                                 ^
cave.cpp:64:5: note: in expansion of macro '_foreq'
   64 |     _foreq(i, l, r) if(!old[i]) S[i] = !S[i];
      |     ^~~~~~
cave.cpp: In function 'void exploreCave(int)':
cave.cpp:25:31: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   25 | #define _for(a, b, c) for(int (a) = (b); (a) < (c); ++(a))
      |                               ^
cave.cpp:68:5: note: in expansion of macro '_for'
   68 |     _for(j, 0, n){ // randam, kuris kontroliuoja j-tasias duris
      |     ^~~~
cave.cpp:82:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   82 |         if(!wasOpen) keisk(k, k); old[k] = 1;
      |         ^~
cave.cpp:82:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   82 |         if(!wasOpen) keisk(k, k); old[k] = 1;
      |                                   ^~~

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