제출 #412368

#제출 시각아이디문제언어결과실행 시간메모리
412368losmi247동굴 (IOI13_cave)C++14
33 / 100
192 ms460 KiB
#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 = 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; } } /*for(int j = 0; j < n; j++){ if(odg1[j] != -1) continue; niz[j] ^= 1; int y = tryCombination(niz); if(y > i || 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 > i || 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 > i || 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(); }

컴파일 시 표준 에러 (stderr) 메시지

cave.cpp: In function 'void zasve()':
cave.cpp:123:49: 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 = j*sz; h < (j+1)*sz && h < moze.size(); h++){ /// ovaj blok izmenis
      |                                               ~~^~~~~~~~~~~~~
cave.cpp:129:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                 for(int h = j*sz; h < (j+1)*sz && h < moze.size(); h++){
      |                                                   ~~^~~~~~~~~~~~~
cave.cpp:134:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             for(int h = j*sz; h < (j+1)*sz && h < moze.size(); h++){
      |                                               ~~^~~~~~~~~~~~~
cave.cpp:140:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         for(int h = kojiblok*sz; h < (kojiblok+1)*sz && h < moze.size(); h++){
      |                                                         ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...