oj.uz

답안 #417477

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
417477 2021-06-03T19:00:18 Z iulia2100 Minerals (JOI19_minerals) C++14
40 / 100
 1000 ms 3228 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;
            }
            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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -