oj.uz

Submission #1002137

# Submission time Handle Problem Language Result Execution time Memory
1002137 2024-06-19T10:19:59 Z overwatch9 Cave (IOI13_cave) C++17
0 / 100
 135 ms 604 KB 
#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

void exploreCave(int N) {
    vector <int> need_to_find;
    for (int i = 0; i < N; i++)
        need_to_find.push_back(i);
    int s[N+1], d[N+1];
    int d_inv[N+1]; // the switch that controls door i
    for (int i = 0; i < N; i++) {
        int query[N+1];
        fill(query, query + N + 1, 0);
        for (int j = 0; j < i; j++) {
            query[d_inv[j]] = s[d_inv[j]];
        }
        // if (i == 1) {
        //     cout << "QUERY: ";
        //     for (int j = 0; j < N; j++)
        //         cout << query[j] << ' ';
        //     cout << '\n';
        // }
        int sz = need_to_find.size();
        // keep half of the positions of the remaining
        int l = 0, r = sz - 1;
        int correct_pos = 0;
        int state = 2;
        while (l < r) {
            int mid = (l + r) / 2;
            // if (i == 1) {
            //     cout << "QUERY: ";
            //     for (int j = 0; j < N; j++)
            //         cout << query[j] << ' ';
            //     cout << '\n';
            // }
            for (int j = 0; j <= mid; j++)
                query[need_to_find[j]] = 2;
            // if (i == 1) {
            //     cout << "QUERY: ";
            //     for (int j = 0; j < N; j++)
            //         cout << query[j] << ' ';
            //     cout << '\n';
            // }
            int res = tryCombination(query);
            for (int j = 0; j <= mid; j++)
                query[need_to_find[j]] = 0;
            int res2 = tryCombination(query);
            
            // if (i == 0) {
            //     cout << "RANGE: " << l << ' ' << r << '\n';
            //     cout << "RES: " << res << ' ' << res2 << ' ' << '\n';
            // }
            if ((min(res, res2) == -1 && max(res, res2) <= i) || (min(res, res2) != -1 && min(res, res2) <= i && max(res, res2) > i)) {
                r = mid;
                correct_pos = mid;
                if (res > i || res == -1)
                    state = 1;
                else
                    state = 0;
            } else {
                l = mid + 1;
            }
        }
        if (state == 2) {
            query[need_to_find[l]] = 1;
            int res = tryCombination(query);
            if (res == -1 || res > i)
                state = 1;
            else
                state = 0;
        }
        // cout << i << ": " << l << " state: " << state << '\n';
        s[need_to_find[l]] = state;
        d[need_to_find[l]] = i;
        d_inv[i] = need_to_find[l];
        need_to_find.erase(need_to_find.begin() + l);
        // cout << "MODIFED: ";
        // for (auto j : need_to_find)
        //     cout << j << ' ';
        // cout << '\n';
    }
    answer(s, d);
}

Compilation message

cave.cpp: In function 'void exploreCave(int)':
cave.cpp:26:13: warning: variable 'correct_pos' set but not used [-Wunused-but-set-variable]
   26 |         int correct_pos = 0;
      |             ^~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 600 KB too much calls on tryCombination()
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 604 KB too much calls on tryCombination()
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Answer is wrong
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Answer is wrong
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 600 KB too much calls on tryCombination()
2 Halted 0 ms 0 KB -