Submission #417449

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
417449	2021-06-03T17:51:18 Z	iulia2100	Minerals (JOI19_minerals)	C++14	40 / 100	962 ms	3052 KB

minerals

#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];

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 (!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)
                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]);
            } else  {
                last_ans = Query(index[i]);
                interval[i].st = other_half_st;
                interval[i].dr = other_half_dr;
            }
        }
    }
    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	200 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct

Subtask #2
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	328 KB	Output is correct
2	Correct	13 ms	488 KB	Output is correct
3	Correct	38 ms	584 KB	Output is correct
4	Correct	170 ms	992 KB	Output is correct
5	Correct	612 ms	1560 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	200 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	4 ms	328 KB	Output is correct
6	Correct	13 ms	488 KB	Output is correct
7	Correct	38 ms	584 KB	Output is correct
8	Correct	170 ms	992 KB	Output is correct
9	Correct	612 ms	1560 KB	Output is correct
10	Correct	3 ms	328 KB	Output is correct
11	Correct	224 ms	1172 KB	Output is correct
12	Correct	530 ms	1616 KB	Output is correct
13	Correct	225 ms	1636 KB	Output is correct
14	Correct	216 ms	1556 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	200 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	4 ms	328 KB	Output is correct
6	Correct	13 ms	488 KB	Output is correct
7	Correct	38 ms	584 KB	Output is correct
8	Correct	170 ms	992 KB	Output is correct
9	Correct	612 ms	1560 KB	Output is correct
10	Correct	3 ms	328 KB	Output is correct
11	Correct	224 ms	1172 KB	Output is correct
12	Correct	530 ms	1616 KB	Output is correct
13	Correct	225 ms	1636 KB	Output is correct
14	Correct	216 ms	1556 KB	Output is correct
15	Incorrect	962 ms	3052 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	200 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	4 ms	328 KB	Output is correct
6	Correct	13 ms	488 KB	Output is correct
7	Correct	38 ms	584 KB	Output is correct
8	Correct	170 ms	992 KB	Output is correct
9	Correct	612 ms	1560 KB	Output is correct
10	Correct	3 ms	328 KB	Output is correct
11	Correct	224 ms	1172 KB	Output is correct
12	Correct	530 ms	1616 KB	Output is correct
13	Correct	225 ms	1636 KB	Output is correct
14	Correct	216 ms	1556 KB	Output is correct
15	Incorrect	962 ms	3052 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	200 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	4 ms	328 KB	Output is correct
6	Correct	13 ms	488 KB	Output is correct
7	Correct	38 ms	584 KB	Output is correct
8	Correct	170 ms	992 KB	Output is correct
9	Correct	612 ms	1560 KB	Output is correct
10	Correct	3 ms	328 KB	Output is correct
11	Correct	224 ms	1172 KB	Output is correct
12	Correct	530 ms	1616 KB	Output is correct
13	Correct	225 ms	1636 KB	Output is correct
14	Correct	216 ms	1556 KB	Output is correct
15	Incorrect	962 ms	3052 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	200 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	4 ms	328 KB	Output is correct
6	Correct	13 ms	488 KB	Output is correct
7	Correct	38 ms	584 KB	Output is correct
8	Correct	170 ms	992 KB	Output is correct
9	Correct	612 ms	1560 KB	Output is correct
10	Correct	3 ms	328 KB	Output is correct
11	Correct	224 ms	1172 KB	Output is correct
12	Correct	530 ms	1616 KB	Output is correct
13	Correct	225 ms	1636 KB	Output is correct
14	Correct	216 ms	1556 KB	Output is correct
15	Incorrect	962 ms	3052 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	200 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	4 ms	328 KB	Output is correct
6	Correct	13 ms	488 KB	Output is correct
7	Correct	38 ms	584 KB	Output is correct
8	Correct	170 ms	992 KB	Output is correct
9	Correct	612 ms	1560 KB	Output is correct
10	Correct	3 ms	328 KB	Output is correct
11	Correct	224 ms	1172 KB	Output is correct
12	Correct	530 ms	1616 KB	Output is correct
13	Correct	225 ms	1636 KB	Output is correct
14	Correct	216 ms	1556 KB	Output is correct
15	Incorrect	962 ms	3052 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	200 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	200 KB	Output is correct
5	Correct	4 ms	328 KB	Output is correct
6	Correct	13 ms	488 KB	Output is correct
7	Correct	38 ms	584 KB	Output is correct
8	Correct	170 ms	992 KB	Output is correct
9	Correct	612 ms	1560 KB	Output is correct
10	Correct	3 ms	328 KB	Output is correct
11	Correct	224 ms	1172 KB	Output is correct
12	Correct	530 ms	1616 KB	Output is correct
13	Correct	225 ms	1636 KB	Output is correct
14	Correct	216 ms	1556 KB	Output is correct
15	Incorrect	962 ms	3052 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Submission #417449

Compilation message