Submission #542866

#	Time	Username	Problem	Language	Result	Execution time	Memory
542866		Vladth11	Cave (IOI13_cave)	C++14	25 / 100	1033 ms	768 KiB

cave

#include <bits/stdc++.h>
#include "cave.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 5001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll base = 13137;
const ll nr_of_bits = 16;

int used[NMAX];
int correct[NMAX];
int coresp[NMAX];
int sol[NMAX];
int act;
int combination[NMAX];

void exploreCave(int N) {
    for(int i = 0; i < N; i++) {
        act = i;
        vector <int> notUsed;
        for(int j = 0; j < N; j++)
            combination[j] = 1;
        for(int j = 0; j < i; j++) {
            combination[coresp[j]] = correct[coresp[j]];
        }
        for(int j = 0; j < N; j++) {
            if(!used[j])
                notUsed.push_back(j);
        }
        int r = -1, pas = (1 << 12);
        int cv = tryCombination(combination);
        while(pas) {
            if(r + pas < notUsed.size()) {
                for(int j = 0; j < N; j++)
                    combination[j] = 1;
                for(int j = 0; j < i; j++) {
                    combination[coresp[j]] = correct[coresp[j]];
                }
                for(int j = 0; j <= r + pas; j++) {
                    combination[notUsed[j]] ^= 1;
                }
                int rez = tryCombination(combination);
                if(cv == i && rez == i){
                    r += pas;
                }else if(cv != i && rez > i){
                    r += pas;
                }
            }
            pas /= 2;
        }
        r++;
        coresp[i] = notUsed[r];
        used[coresp[i]] = 1;
        sol[coresp[i]] = i;
        if(cv == i) {
            correct[coresp[i]] = 0;
        } else {
            correct[coresp[i]] = 1;
        }
    }
    answer(correct, sol);
}

Compilation message (stderr)

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:42:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if(r + pas < notUsed.size()) {
      |                ~~~~~~~~^~~~~~~~~~~~~~~~

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