oj.uz

Submission #417465

# Submission time Handle Problem Language Result Execution time Memory
417465 2021-06-03T18:34:59 Z iulia2100 Minerals (JOI19_minerals) C++14
40 / 100
 930 ms 3200 KB 
#include <iostream>
#include <set>
#include "minerals.h"

using namespace std;

//ifstream cin ("idk.in");
//ofstream cout ("idk.out");

const int N = 43005;

struct idk {
    int st, dr;
} interval[N + N];

int n, last_ans;
int index[N];
bool in_set[N + N], answered[N + N];

set <int> s;

void bs(int st, int dr, int other_half_st, int other_half_dr) {
    int x = last_ans;
    if (other_half_st > dr) { //sunt in partea stanga. Daca sunt in dreapta cunosc deja intervalele
        auto it = s.begin();
        while (it != s.end())   {
            if ((*it) >= st && (*it) <= dr)   {
                ++it;
                continue;
            }
            x = Query(index[(*it)]);
            in_set[(*it)] = false;
            last_ans = x;
            it = s.erase(it);
        }
        for (int i = st; i <= dr; ++i)  {
            if (answered[i])    {
                if (in_set[i]) {
                    s.erase(i);
                    in_set[i] = false;
                    x = Query(index[i]);
                    last_ans = x;
                }
                continue;
            }
            if (!in_set[i]) {
                s.insert(i);
                in_set[i] = true;
                x = Query(index[i]);
                last_ans = x;
            }
        }
        for (int i = n + 1; i <= n + n; ++i)    {
            if (interval[i].dr < st || interval[i].st > dr || answered[i])
                continue;
            int aux = Query(index[i]);
            last_ans = aux;
            if (aux == x)   {
                interval[i].st = st, interval[i].dr = dr;
                last_ans = Query(index[i]);
                if (st == dr)
                    answered[i] = answered[interval[i].st] = true;
            } else  {
                last_ans = Query(index[i]);
                interval[i].st = other_half_st;
                interval[i].dr = other_half_dr;
                if (st == dr)
                    answered[i] = answered[interval[i].st] = true;
            }
        }
    }
    if (st == dr)   {
        return;
    }
    bs(st, (st + dr) / 2, (st + dr) / 2 + 1, dr);
    bs((st + dr) / 2 + 1, dr, st, (st + dr) / 2);
}

void find_index()   {
    int last = 0, nd = n, st = 0;
    for (int i = 1; i <= n + n; ++i)    {
        int x = Query(i);
        last_ans = x;
        if (x == last)  {
            last_ans = Query(i);
            continue;
        }
        in_set[i] = true;
        last = x;
    }
    for (int i = 1; i <= n + n; ++i)    {
        if (!in_set[i])
            index[++nd] = i;
        else index[++st] = i;
    }
    for (int i = 1; i <= n; ++i)    {
        in_set[i] = true;
        s.insert(i);
        in_set[i + n] = false;
    }
//    cout << '\n';
//    for (int i = 1; i <= n + n; ++i)
//        cout << index[i] << ' ';
}

void Solve(int aux_n)   {
    n = aux_n;
    find_index();
    for (int i = 1; i <= n; ++i)
        interval[i + n] = {1, n};
    bs(1, n / 2, n / 2 + 1, n);
    bs(n / 2 + 1, n, 1, n / 2);
    for (int i = 1; i <= n; ++i)    {
        Answer(index[interval[i + n].st], index[i + n]);
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 408 KB Output is correct
2 Correct 13 ms 456 KB Output is correct
3 Correct 50 ms 664 KB Output is correct
4 Correct 204 ms 968 KB Output is correct
5 Correct 744 ms 1588 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 6 ms 408 KB Output is correct
6 Correct 13 ms 456 KB Output is correct
7 Correct 50 ms 664 KB Output is correct
8 Correct 204 ms 968 KB Output is correct
9 Correct 744 ms 1588 KB Output is correct
10 Correct 4 ms 328 KB Output is correct
11 Correct 276 ms 1192 KB Output is correct
12 Correct 632 ms 1764 KB Output is correct
13 Correct 236 ms 1756 KB Output is correct
14 Correct 238 ms 1700 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 6 ms 408 KB Output is correct
6 Correct 13 ms 456 KB Output is correct
7 Correct 50 ms 664 KB Output is correct
8 Correct 204 ms 968 KB Output is correct
9 Correct 744 ms 1588 KB Output is correct
10 Correct 4 ms 328 KB Output is correct
11 Correct 276 ms 1192 KB Output is correct
12 Correct 632 ms 1764 KB Output is correct
13 Correct 236 ms 1756 KB Output is correct
14 Correct 238 ms 1700 KB Output is correct
15 Incorrect 930 ms 3200 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 6 ms 408 KB Output is correct
6 Correct 13 ms 456 KB Output is correct
7 Correct 50 ms 664 KB Output is correct
8 Correct 204 ms 968 KB Output is correct
9 Correct 744 ms 1588 KB Output is correct
10 Correct 4 ms 328 KB Output is correct
11 Correct 276 ms 1192 KB Output is correct
12 Correct 632 ms 1764 KB Output is correct
13 Correct 236 ms 1756 KB Output is correct
14 Correct 238 ms 1700 KB Output is correct
15 Incorrect 930 ms 3200 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 6 ms 408 KB Output is correct
6 Correct 13 ms 456 KB Output is correct
7 Correct 50 ms 664 KB Output is correct
8 Correct 204 ms 968 KB Output is correct
9 Correct 744 ms 1588 KB Output is correct
10 Correct 4 ms 328 KB Output is correct
11 Correct 276 ms 1192 KB Output is correct
12 Correct 632 ms 1764 KB Output is correct
13 Correct 236 ms 1756 KB Output is correct
14 Correct 238 ms 1700 KB Output is correct
15 Incorrect 930 ms 3200 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 6 ms 408 KB Output is correct
6 Correct 13 ms 456 KB Output is correct
7 Correct 50 ms 664 KB Output is correct
8 Correct 204 ms 968 KB Output is correct
9 Correct 744 ms 1588 KB Output is correct
10 Correct 4 ms 328 KB Output is correct
11 Correct 276 ms 1192 KB Output is correct
12 Correct 632 ms 1764 KB Output is correct
13 Correct 236 ms 1756 KB Output is correct
14 Correct 238 ms 1700 KB Output is correct
15 Incorrect 930 ms 3200 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 6 ms 408 KB Output is correct
6 Correct 13 ms 456 KB Output is correct
7 Correct 50 ms 664 KB Output is correct
8 Correct 204 ms 968 KB Output is correct
9 Correct 744 ms 1588 KB Output is correct
10 Correct 4 ms 328 KB Output is correct
11 Correct 276 ms 1192 KB Output is correct
12 Correct 632 ms 1764 KB Output is correct
13 Correct 236 ms 1756 KB Output is correct
14 Correct 238 ms 1700 KB Output is correct
15 Incorrect 930 ms 3200 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 6 ms 408 KB Output is correct
6 Correct 13 ms 456 KB Output is correct
7 Correct 50 ms 664 KB Output is correct
8 Correct 204 ms 968 KB Output is correct
9 Correct 744 ms 1588 KB Output is correct
10 Correct 4 ms 328 KB Output is correct
11 Correct 276 ms 1192 KB Output is correct
12 Correct 632 ms 1764 KB Output is correct
13 Correct 236 ms 1756 KB Output is correct
14 Correct 238 ms 1700 KB Output is correct
15 Incorrect 930 ms 3200 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -