Submission #384088

#	Time	Username	Problem	Language	Result	Execution time	Memory
384088		mehrdad_sohrabi	Cave (IOI13_cave)	C++14	100 / 100	970 ms	876 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
/// 500 485 462 A4
using namespace std;
typedef int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
const int N=5e3+10;
/*
void answer(int S[], int D[]) {
    for (int i=0;i<10;i++){
        cout << S[i] << " ";
    }
    cout << endl;
    for (int i=0;i<10;i++){
        cout << D[i] << " ";
    }
}
ll tryCombination(int S[]) {
    for (int i=0;i<10;i++){
        if (S[i]==1) return i;
    }
    return -1;
}
*/
ll state[N];
ll mat[N];
ll vis[N];
void exploreCave(int N) {
    /* ... */
    ll n=N;
    for (int i=0;i<n;i++){
        vector <int> a;
        for (int j=0;j<n;j++) if (!vis[j]) a.pb(j);
        ll z=tryCombination(state);
        ll l=0,r=a.size();
        while(r-l>1){
            ll mid=(r+l)/2;
            for (int j=mid;j<a.size();j++) state[a[j]]=1;
            ll d=tryCombination(state);
            if ((d==i && z!=i) || (d!=i && z==i)) l=mid;
            else r=mid;
            for (int j=mid;j<a.size();j++) state[a[j]]=0;
        }
        l=a[l];
        mat[l]=i;
        vis[l]=1;
        if (z==i) state[l]=1;
    }
    answer(state,mat);
}
/*
int main(){
    ll n;
    cin >> n;
    exploreCave(N);
}
*/

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:48:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for (int j=mid;j<a.size();j++) state[a[j]]=1;
      |                            ~^~~~~~~~~
cave.cpp:52:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for (int j=mid;j<a.size();j++) state[a[j]]=0;
      |                            ~^~~~~~~~~

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