Submission #1033917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033917		shjeong	Cave (IOI13_cave)	C++17	100 / 100	245 ms	944 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef long long ll;
void exploreCave(int N) {
    int *s = (int*)malloc(N*sizeof(int));
    int *ans = (int*)malloc(N*sizeof(int));   //s[i] = j : i번 문은 j번 스위치 / ans[i] = j : i번 스위치는 j
    int *invs = (int*)malloc(N*sizeof(int));
    vector<bool> vis(N);
    for(int i = 0 ; i < N ; i++){
        int *tmp = (int*)malloc(N*sizeof(int));
        for(int j = 0 ; j < N ; j++)tmp[j] = 0;
        vector<ll> idx;
        for(int j = 0 ; j < N ; j++){
            if(!vis[j])idx.push_back(j);
        }
        for(int j = 0 ; j < i ; j++)tmp[s[j]] = ans[s[j]];
        ll x = tryCombination(tmp);
        bool f = (x==i);   //x==i : 막힘. 즉 다 0으로 했는데 막혔으므로 1이어야함. 아니면 반대
        ll l = 0, r = (int)idx.size()-1;
        while(l < r){
            ll mid = l+r>>1;
            for(int j = l ; j <= mid ; j++)tmp[idx[j]] = 0;
            for(int j = mid+1 ; j <= r ; j++)tmp[idx[j]] = 1;
            ll x = tryCombination(tmp);
            if(x==i){   //막힘. 즉 f여야 켜지는데 아니므로 f 반대 방향에 있음. 아니면 반대
                if(f==1)r = mid;
                else l = mid+1;
            }
            else{   //안막힘. 즉 f여야 켜지는데 맞으므로 f 방향에 있음. 아니면 반대
                if(f==1)l = mid+1;
                else r = mid;
            }
        }
        ans[idx[r]] = f;
        s[i] = idx[r];
        invs[idx[r]] = i;
        vis[idx[r]] = 1;
        free(tmp);
    }
    answer(ans,invs);
    free(ans); free(s);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:22:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             ll mid = l+r>>1;
      |                      ~^~

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