Submission #412353

#	Time	Username	Problem	Language	Result	Execution time	Memory
412353		losmi247	Cave (IOI13_cave)	C++14	0 / 100	82 ms	452 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);
    int *treba = (int*)malloc(sizeof(int)*n);
    for(int i = 0; i < n; i++) niz[i] = 0;
    for(int i = 0; i < n; i++) treba[i] = 0;
    for(int i = 0; i < n; i++) odg1[i] = -1;


    for(int i = 0; i < n; i++){   /// gledas i-ta vrata, trazis kako treba da stoji i ko je kontrolise
        /// kako treba da mu stoji svic?
        for(int j = 0; j < n; j++){
            if(odg1[j] == -1) niz[j] = 0;
        }
        int x = tryCombination(niz);
        int svic;
        //assert(x >= i || x == -1);
        if(x > i || x == -1) svic = 0;
        else svic = 1;

        if(svic == 0){
            for(int j = 0; j < n; j++){
                if(odg1[j] == -1) niz[j] = 1;
            }
        }


        for(int j = 0; j < n; j++){
            if(odg1[j] != -1) continue;
            niz[j] ^= 1;
            int y = tryCombination(niz);
            if(y > x || y == -1){
                odg1[j] = i;
                treba[j] = svic;
                break;
            }
            niz[j] ^= 1;
        }

        /// koji je njegov svic?
        /*vector <int> moze;
        for(int j = 0; j < n; j++){
            if(odg1[j] == -1) moze.push_back(j);
        }

        int sz = sqrt(moze.size()); /// velicina blokova
        int brb = (moze.size()+sz-1)/sz;
        int kojiblok = -1;
        for(int j = 0; j < brb; j++){
            for(int h = j*sz; h < (j+1)*sz && h < moze.size(); h++){ /// ovaj blok izmenis
                niz[moze[h]] ^= 1;
            }
            int y = tryCombination(niz);
            if(y > x || y == -1){
                kojiblok = j;
                for(int h = j*sz; h < (j+1)*sz && h < moze.size(); h++){
                    niz[moze[h]] ^= 1;
                }
                break;
            }
            for(int h = j*sz; h < (j+1)*sz && h < moze.size(); h++){
                niz[moze[h]] ^= 1;
            }
        }

        bool naso = 0;
        for(int h = kojiblok*sz; h < (kojiblok+1)*sz && h < moze.size(); h++){
            niz[moze[h]] ^= 1;
            int y = tryCombination(niz);
            if(y > x || y == -1){
                odg1[moze[h]] = i;
                treba[moze[h]] = svic;
                naso = 1;
                break;
            }
            niz[moze[h]] ^= 1;
        }
        assert(naso);*/
    }

    answer(treba,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();
}

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