Submission #412132

#	Time	Username	Problem	Language	Result	Execution time	Memory
412132		losmi247	Cave (IOI13_cave)	C++14	46 / 100	29 ms	412 KiB

cave

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

int n;



/*int *prvi,*drugi;
int *kojisvic;
int tryCombination(int *S){
    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);
}

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] = 0;
    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;
        }
        for(int j = 0; j < n; j++){
            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;



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

zasve();
    return;

    znamred();
}

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

    int gh;
    cin >> gh;
    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];
    for(int i = 0; i < gh; i++){ cin >> drugi[i]; kojisvic[drugi[i]] = i; }

    exploreCave(gh);
}*/

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