Submission #412372

#	Time	Username	Problem	Language	Result	Execution time	Memory
412372		losmi247	Cave (IOI13_cave)	C++14	100 / 100	527 ms	580 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);
}

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 = 0;
        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;
            }
        }

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

        int l = 0,r = moze.size()-1;
        while(l < r){
            int mid = l+(r-l)/2;
            for(int h = l; h <= mid; h++){
                niz[moze[h]] ^= 1;
            }
            int y = tryCombination(niz);
            for(int h = l; h <= mid; h++){
                niz[moze[h]] ^= 1;
            }
            if(y > i || y == -1){
                r = mid;
            }
            else{
                l = mid+1;
            }
        }

        odg1[moze[l]] = i;
        treba[moze[l]] = svic;
        niz[moze[l]] ^= 1;
    }

    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: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24