제출 #1139218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139218		davele	Cave (IOI13_cave)	C++20	100 / 100	218 ms	576 KiB

cave

#ifndef davele
#include "cave.h"
#endif // davele

#include <bits/stdc++.h>
#define pq priority_queue
#define ll long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(i) (1ll<<(i))
#define next __next
#define pos __pos
using namespace std;
const double PI = acos(-1);
/*const int mod = ;

void sub (int&a, const int&b){
    a-=b;
    if (a<0) a+=mod;
}

void mul (int&a, const int&b){
    a = (1ll*a*b)%mod;
}

void add (int&a, const int&b){
    a+=b;
    if (a>=mod) a-=mod;
}*/

bool minimize (ll&a, const ll&b){
    if (a<=b) return false;
    a=b;
    return true;
}

bool maximize (ll&a, const ll&b){
    if (a>=b) return false;
    a=b;
    return true;
}
////////////////////////////////////////////////////////////////////////////////////////////

bool vis[5005];
int locat[5005], stat[5005];

#ifndef davele

void exploreCave(int n) {
    /* ... */
    memset(locat, 0, sizeof(locat));
    memset(stat, 0, sizeof(stat));
    memset(vis, false, sizeof(vis));
    for (int i=0; i<n; i++){
        vector <int> rem;
        for (int j=0; j<n; j++) if (vis[j]==false) rem.pb(j);
        for (int x:rem) stat[x] = 0;
        int curkey = 0;
        if (tryCombination(stat)==i) curkey = 1;
        int l = 0, r = rem.size()-1, ret = rem.size()-1;
        while (l<=r){
            int mid = (l+r)/2;
            for (int j=0; j<=mid; j++) stat[rem[j]] = curkey;
            for (int j=mid+1; j<rem.size(); j++) stat[rem[j]] = 1-curkey;
            if (tryCombination(stat)==i){
                l = mid+1;
            }
            else{
                ret = rem[mid];
                r = mid-1;
            }
        }
        vis[ret] = true;
        stat[ret] = curkey;
        locat[ret] = i;
    }
    answer(stat, locat);
}
#endif // davele


#ifdef davele
int n;
int realstat[5005], reallocat[5005], key[5005];

int tryCombination(int stat[]){
//    for (int i=0; i<n; i++) cerr<<stat[i]<<" ";
//    cerr<<"\n";
    for (int i=0; i<n; i++){
        if (stat[key[i]]!=realstat[key[i]]) return i;
    }
    return -1;
}

void answer (int stat[], int locat[]){
    for (int i=0; i<n; i++) cout<<stat[i]<<" ";
    cout<<"\n";
    for (int i=0; i<n; i++) cout<<locat[i]<<" ";
}

signed main(){
    cin>>n;
    for (int i=0; i<n; i++) cin>>realstat[i];
    for (int i=0; i<n; i++) cin>>reallocat[i];
    for (int i=0; i<n; i++) key[reallocat[i]] = i;
//    for (int i=0; i<n; i++) cerr<<key[i]<<" ";
//    cerr<<"\n";
    memset(locat, 0, sizeof(locat));
    memset(stat, 0, sizeof(stat));
    memset(vis, false, sizeof(vis));
    for (int i=0; i<n; i++){
        vector <int> rem;
        for (int j=0; j<n; j++) if (vis[j]==false) rem.pb(j);
        for (int x:rem) stat[x] = 0;
        int curkey = 0;
        if (tryCombination(stat)==i) curkey = 1;
        int l = 0, r = rem.size()-1, ret = rem.size()-1;
        while (l<=r){
            int mid = (l+r)/2;
            for (int j=0; j<=mid; j++) stat[rem[j]] = curkey;
            for (int j=mid+1; j<rem.size(); j++) stat[rem[j]] = 1-curkey;
            if (tryCombination(stat)==i){
                l = mid+1;
            }
            else{
                ret = rem[mid];
                r = mid-1;
            }
        }
        vis[ret] = true;
        stat[ret] = curkey;
        locat[ret] = i;
        cerr<<ret<<" "<<curkey<<"\n";
    }
    answer(stat, locat);
}

#endif // davele

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