Submission #412285

#	Time	Username	Problem	Language	Result	Execution time	Memory
412285		losmi247	Cave (IOI13_cave)	C++14	25 / 100	124 ms	468 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] = 0;
    for(int i = 0; i < n; i++) odg1[i] = -1;

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

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

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

        vector <int> moze;
        for(int j = 0; j < n; j++){  /// sigurno samo oni > x sada
            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;
            }
        }

        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]] = x;
                break;
            }
            niz[moze[h]] ^= 1;
        }

        /*for(int j = 0; j < n; j++){ /// ko upravlja vratima x?
            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;
}*/

Compilation message (stderr)

cave.cpp: In function 'void zasve()':
cave.cpp:107:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             for(int h = j*sz; h < (j+1)*sz && h < moze.size(); h++){ /// ovaj blok izmenis
      |                                               ~~^~~~~~~~~~~~~
cave.cpp:113:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 for(int h = j*sz; h < (j+1)*sz && h < moze.size(); h++){
      |                                                   ~~^~~~~~~~~~~~~
cave.cpp:118:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             for(int h = j*sz; h < (j+1)*sz && h < moze.size(); h++){
      |                                               ~~^~~~~~~~~~~~~
cave.cpp:123:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int h = kojiblok*sz; h < (kojiblok+1)*sz && h < moze.size(); h++){
      |                                                         ~~^~~~~~~~~~~~~

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