oj.uz

Submission #975028

# Submission time Handle Problem Language Result Execution time Memory
975028 2024-05-04T10:20:47 Z rahidilbayramli Cave (IOI13_cave) C++17
12 / 100
 219 ms 764 KB 
#include "cave.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define pb push_back
#define f first
#define s second
using namespace std;
using namespace __gnu_pbds;
typedef tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
void exploreCave(int N) {
    int n = N, i, j;
    int isfound[n], f[n], sw[n], fa[n];
    for(i = 0; i < n; i++)
    {
        f[i] = 0;
        isfound[i] = 0;
        sw[i] = 0;
    }
    for(i = 0; i < n; i++)
    {
        int ans = n;
        int ask = tryCombination(f);
        if(ask == i){
            int l = i, r = n - 1;
            while(l <= r)
            {
                for(j = 0; j < n; j++)
                    fa[j] = f[j];
                int mid = (l + r) / 2;
                for(j = 0; j <= mid; j++)
                {
                    if(!isfound[j])
                        fa[j] = 1 - f[j];
                }
                int res = tryCombination(fa);
                if(res != i)
                {
                    ans = min(ans, mid);
                    r = mid - 1;
                }
                else
                    l = mid + 1;
            }
            isfound[ans] = 1;
            sw[ans] = i;
            f[ans] = 1 - f[ans];
        }
        else
        {
            int l = i, r = n - 1;
            while(l <= r)
            {
                for(j = 0; j < n; j++)
                    fa[j] = f[j];
                int mid = (l + r) / 2;
                for(j = 0; j <= mid; j++)
                {
                    if(!isfound[j])
                        fa[j] = 1 - f[j];
                }
                int res = tryCombination(fa);
                if(res == i)
                {
                    ans = min(ans, mid);
                    r = mid - 1;
                }
                else
                    l = mid + 1;
            }
            isfound[ans] = 1;
            sw[ans] = i;
        }
    }
    answer(f, sw);
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 348 KB Output is correct
2 Correct 131 ms 556 KB Output is correct
3 Correct 184 ms 348 KB Output is correct
4 Correct 146 ms 604 KB Output is correct
5 Correct 194 ms 600 KB Output is correct
6 Correct 219 ms 576 KB Output is correct
7 Correct 200 ms 576 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 172 ms 572 KB Output is correct
13 Correct 194 ms 764 KB Output is correct
14 Correct 175 ms 600 KB Output is correct

Subtask #2
0 / 13.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 348 KB Output is correct
2 Correct 131 ms 556 KB Output is correct
3 Correct 184 ms 348 KB Output is correct
4 Correct 146 ms 604 KB Output is correct
5 Correct 194 ms 600 KB Output is correct
6 Correct 219 ms 576 KB Output is correct
7 Correct 200 ms 576 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 172 ms 572 KB Output is correct
13 Correct 194 ms 764 KB Output is correct
14 Correct 175 ms 600 KB Output is correct
15 Correct 190 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Incorrect 172 ms 580 KB Answer is wrong
18 Halted 0 ms 0 KB -