제출 #412157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
412157		losmi247	동굴 (IOI13_cave)	C++14	21 / 100	32 ms	480 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
using namespace std;
typedef long long ll;
const int N = 5002;

int n;


/*int puta = 0;
int *prvi,*drugi;
int *kojisvic;
int tryCombination(int *S){
    puta++;
    for(int i = 0; i < n; i++){
        if(S[kojisvic[i]] != prvi[kojisvic[i]]) return i;
    }
    return -1;
}

void answer(int *S,int *D){
    for(int i = 0; i < n; i++){
        if(S[i] != prvi[i]){
            cout << "WA1" << endl;
            exit(0);
        }
    }
    for(int i = 0; i < n; i++){
        if(D[i] != drugi[i]){
            cout << "WA2" << endl;

            for(int i = 0; i < n; i++){
                cout << D[i] << " ";
            }
            cout << endl;

            exit(0);
        }
    }
    cout << "OK" << endl;
}*/




void znamred(){
    int *niz = (int*)malloc(sizeof(int)*n);
    int *odg1 = (int*)malloc(sizeof(int)*n);
    for(int i = 0; i < n; i++){ niz[i] = 0; odg1[i] = i; }

    while(1){
        int x = tryCombination(niz);
        if(x == -1) break;
        niz[x] ^= 1;
    }

    answer(niz,odg1);
}

void znamkod(){
    int *niz = (int*)malloc(sizeof(int)*n);
    int *odg1 = (int*)malloc(sizeof(int)*n);
    for(int i = 0; i < n; i++) niz[i] = 0;

    for(int i = 0; i < n; i++){
        niz[i] = 1;
        odg1[i] = tryCombination(niz);
        niz[i] = 0;
    }

    answer(niz,odg1);
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void zasve(){
    int *niz = (int*)malloc(sizeof(int)*n);
    int *odg1 = (int*)malloc(sizeof(int)*n);
    for(int i = 0; i < n; i++) niz[i] = /*rnd()%2*/ /*(i > n/2)*/ 1;
    for(int i = 0; i < n; i++) odg1[i] = -1;

    while(1){
        int x = tryCombination(niz);

        if(x == -1){ /// sad su sva ugasena, nasao si S(i) za sve
            break;
        }

        vector <int> moze;
        for(int j = 0; j < n; j++){
            if(odg1[j] == -1) moze.push_back(j);
        }
        shuffle(moze.begin(),moze.end(),rnd);

        for(/*int j = 0; j < n; j++*/ auto j : moze){
            if(odg1[j] != -1) continue;

            niz[j] ^= 1;
            int y = tryCombination(niz);
            if(y > x || y == -1){ /// znaci da svic j upravlja vratima x
                odg1[j] = x;
                break;
            }
            if(y < x){
                odg1[j] = y;
            }
            niz[j] ^= 1;
        }
    }
    /// sad znas sve S(i), tj. za niz su ti sva vrata ugasena

    for(int i = 0; i < n; i++){
        if(odg1[i] != -1) continue;
        niz[i] ^= 1;
        odg1[i] = tryCombination(niz);
        niz[i] ^= 1;
    }

    answer(niz,odg1);
}

void exploreCave(int br){
    n = br;

zasve();
    return;

    int *pr = (int*)malloc(sizeof(int)*n);
    for(int i = 0; i < n; i++) pr[i] = 0;
    if(tryCombination(pr) == -1){
        znamkod();
        return;
    }



    znamred();
}

/*int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int gh;
    //cin >> gh;
    gh = 2000;
    prvi = (int*)malloc(sizeof(int)*gh);
    drugi = (int*)malloc(sizeof(int)*gh);
    kojisvic = (int*)malloc(sizeof(int)*gh);
    for(int i = 0; i < gh; i++) cin >> prvi[i]; prvi[i] = 1;
    for(int i = 0; i < gh; i++){ cin >> drugi[i]; drugi[i] = gh-i-1; kojisvic[drugi[i]] = i; }

    exploreCave(gh);

    cout << puta << endl;
}*/

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