Submission #417477

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
417477	2021-06-03T19:00:18 Z	iulia2100	Minerals (JOI19_minerals)	C++14	40 / 100	1000 ms	3228 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], 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;
            }
            if (!answered[(*it)])   {
                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] && !answered[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)   {
                if (st == dr)   {
                    in_set[st] = in_set[i] = true;
                    answered[i] = answered[st] = true;
                } else
                    last_ans = Query(index[i]);
                interval[i].st = st, interval[i].dr = dr;
            } else  {
                if (other_half_st == other_half_dr)   {
                    in_set[other_half_st] = in_set[i] = true;
                    answered[i] = answered[other_half_st] = true;
                    x = aux;
                } 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	252 KB	Output is correct
2	Correct	0 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	4 ms	328 KB	Output is correct
2	Correct	11 ms	492 KB	Output is correct
3	Correct	38 ms	664 KB	Output is correct
4	Correct	159 ms	996 KB	Output is correct
5	Correct	620 ms	1584 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	252 KB	Output is correct
2	Correct	0 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	4 ms	328 KB	Output is correct
6	Correct	11 ms	492 KB	Output is correct
7	Correct	38 ms	664 KB	Output is correct
8	Correct	159 ms	996 KB	Output is correct
9	Correct	620 ms	1584 KB	Output is correct
10	Correct	4 ms	328 KB	Output is correct
11	Correct	227 ms	1208 KB	Output is correct
12	Correct	538 ms	1640 KB	Output is correct
13	Correct	256 ms	1768 KB	Output is correct
14	Correct	233 ms	1600 KB	Output is correct

Subtask #4
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	252 KB	Output is correct
2	Correct	0 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	4 ms	328 KB	Output is correct
6	Correct	11 ms	492 KB	Output is correct
7	Correct	38 ms	664 KB	Output is correct
8	Correct	159 ms	996 KB	Output is correct
9	Correct	620 ms	1584 KB	Output is correct
10	Correct	4 ms	328 KB	Output is correct
11	Correct	227 ms	1208 KB	Output is correct
12	Correct	538 ms	1640 KB	Output is correct
13	Correct	256 ms	1768 KB	Output is correct
14	Correct	233 ms	1600 KB	Output is correct
15	Execution timed out	1046 ms	3228 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	252 KB	Output is correct
2	Correct	0 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	4 ms	328 KB	Output is correct
6	Correct	11 ms	492 KB	Output is correct
7	Correct	38 ms	664 KB	Output is correct
8	Correct	159 ms	996 KB	Output is correct
9	Correct	620 ms	1584 KB	Output is correct
10	Correct	4 ms	328 KB	Output is correct
11	Correct	227 ms	1208 KB	Output is correct
12	Correct	538 ms	1640 KB	Output is correct
13	Correct	256 ms	1768 KB	Output is correct
14	Correct	233 ms	1600 KB	Output is correct
15	Execution timed out	1046 ms	3228 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	252 KB	Output is correct
2	Correct	0 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	4 ms	328 KB	Output is correct
6	Correct	11 ms	492 KB	Output is correct
7	Correct	38 ms	664 KB	Output is correct
8	Correct	159 ms	996 KB	Output is correct
9	Correct	620 ms	1584 KB	Output is correct
10	Correct	4 ms	328 KB	Output is correct
11	Correct	227 ms	1208 KB	Output is correct
12	Correct	538 ms	1640 KB	Output is correct
13	Correct	256 ms	1768 KB	Output is correct
14	Correct	233 ms	1600 KB	Output is correct
15	Execution timed out	1046 ms	3228 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	252 KB	Output is correct
2	Correct	0 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	4 ms	328 KB	Output is correct
6	Correct	11 ms	492 KB	Output is correct
7	Correct	38 ms	664 KB	Output is correct
8	Correct	159 ms	996 KB	Output is correct
9	Correct	620 ms	1584 KB	Output is correct
10	Correct	4 ms	328 KB	Output is correct
11	Correct	227 ms	1208 KB	Output is correct
12	Correct	538 ms	1640 KB	Output is correct
13	Correct	256 ms	1768 KB	Output is correct
14	Correct	233 ms	1600 KB	Output is correct
15	Execution timed out	1046 ms	3228 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	252 KB	Output is correct
2	Correct	0 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	4 ms	328 KB	Output is correct
6	Correct	11 ms	492 KB	Output is correct
7	Correct	38 ms	664 KB	Output is correct
8	Correct	159 ms	996 KB	Output is correct
9	Correct	620 ms	1584 KB	Output is correct
10	Correct	4 ms	328 KB	Output is correct
11	Correct	227 ms	1208 KB	Output is correct
12	Correct	538 ms	1640 KB	Output is correct
13	Correct	256 ms	1768 KB	Output is correct
14	Correct	233 ms	1600 KB	Output is correct
15	Execution timed out	1046 ms	3228 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	252 KB	Output is correct
2	Correct	0 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	4 ms	328 KB	Output is correct
6	Correct	11 ms	492 KB	Output is correct
7	Correct	38 ms	664 KB	Output is correct
8	Correct	159 ms	996 KB	Output is correct
9	Correct	620 ms	1584 KB	Output is correct
10	Correct	4 ms	328 KB	Output is correct
11	Correct	227 ms	1208 KB	Output is correct
12	Correct	538 ms	1640 KB	Output is correct
13	Correct	256 ms	1768 KB	Output is correct
14	Correct	233 ms	1600 KB	Output is correct
15	Execution timed out	1046 ms	3228 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Submission #417477

Compilation message