답안 #486179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486179	2021-11-10T17:28:02 Z	blue	Minerals (JOI19_minerals)	C++17	40 / 100	1000 ms	3552 KB

minerals

#include "minerals.h"
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

using vi = vector<int>;

const int maxN = 43'000;

int N;

vi mushroom(1+2*maxN, 0);

int last_ans = 0;

int sz(vi x)
{
    return int(x.size());
}

void dnc(vi L, vi R, bool bL, bool bR)
{
    // cerr << "dnc " << b << " : ";
    // for(int l:L) cerr << l << ' ';
    // cerr << " | ";
    // for(int r:R) cerr << r << ' ';
    // cerr << "\n";
    if(int(L.size()) == 1)
        Answer(L[0], R[0]);
    else if(int(L.size()) == 2)
    {
        if(!bL) last_ans = Query(L[0]);
        else last_ans = Query(L[1]); //0 is active

        int prev_ans = last_ans;
        last_ans = Query(R[0]);
        if(prev_ans == last_ans)
        {
            Answer(L[0], R[0]);
            Answer(L[1], R[1]);
        }
        else
        {
            Answer(L[0], R[1]);
            Answer(L[1], R[0]);
        }
    }
    else
    {
        int K = int(L.size());

        vi L1, L2;
        for(int i = 0; i < K/2; i++)
            L1.push_back(L[i]);

        for(int i = K/2; i < K; i++)
            L2.push_back(L[i]);


        if(bL)
        {
            for(int l: L2)
                last_ans = Query(l);
        }
        else
        {
            for(int l: L1)
                last_ans = Query(l);
        }

        vi R1, R2;

        for(int r:R)
        {
            if(sz(R1) == sz(L1) && sz(R2) + 1 == sz(L2))
            {
                R2.push_back(r);
            }
            else if(sz(R1) + 1 == sz(L1) && sz(R2) == sz(L2))
            {
                R1.push_back(r);
            }
            else
            {
                int prev_ans = last_ans;
                last_ans = Query(r);
                if(last_ans == prev_ans)
                {
                    R1.push_back(r);
                }
                else
                {
                    R2.push_back(r);
                }
            }
        }

        dnc(L1, R1, 1, !bR);
        dnc(L2, R2, 0, !bR);
    }
}

void Solve(int N_)
{
    N = N_;

    int ct = 0;

    for(int i = 1; i <= 2*N; i++)
    {
        last_ans = Query(i);
        if(last_ans > ct)
        {
            // cerr << "increasing ct = " << ct << " at " << i << '\n';
            ct++;
            mushroom[i] = ct;
            // cerr << i << " : " << mushroom[i] << '\n';
        }
    }

    // cerr << "check\n";

    // for(int i = 1; i <= 2*N; i++) cerr << i << " : " << mushroom[i] << '\n';


    vi leftval, rightval;
    for(int i = 1; i <= 2*N; i++)
    {
        if(mushroom[i])
            leftval.push_back(i);
        else
            rightval.push_back(i);
    }

    dnc(leftval, rightval, 1, 1);
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	584 KB	Output is correct
2	Correct	1 ms	584 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	584 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	712 KB	Output is correct
2	Correct	5 ms	712 KB	Output is correct
3	Correct	13 ms	888 KB	Output is correct
4	Correct	37 ms	1096 KB	Output is correct
5	Correct	106 ms	1636 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	584 KB	Output is correct
2	Correct	1 ms	584 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	584 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	5 ms	712 KB	Output is correct
7	Correct	13 ms	888 KB	Output is correct
8	Correct	37 ms	1096 KB	Output is correct
9	Correct	106 ms	1636 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	57 ms	1436 KB	Output is correct
12	Correct	112 ms	1760 KB	Output is correct
13	Correct	149 ms	1640 KB	Output is correct
14	Correct	98 ms	1772 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	584 KB	Output is correct
2	Correct	1 ms	584 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	584 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	5 ms	712 KB	Output is correct
7	Correct	13 ms	888 KB	Output is correct
8	Correct	37 ms	1096 KB	Output is correct
9	Correct	106 ms	1636 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	57 ms	1436 KB	Output is correct
12	Correct	112 ms	1760 KB	Output is correct
13	Correct	149 ms	1640 KB	Output is correct
14	Correct	98 ms	1772 KB	Output is correct
15	Correct	640 ms	3532 KB	Output is correct
16	Correct	623 ms	3516 KB	Output is correct
17	Execution timed out	1174 ms	3552 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	584 KB	Output is correct
2	Correct	1 ms	584 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	584 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	5 ms	712 KB	Output is correct
7	Correct	13 ms	888 KB	Output is correct
8	Correct	37 ms	1096 KB	Output is correct
9	Correct	106 ms	1636 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	57 ms	1436 KB	Output is correct
12	Correct	112 ms	1760 KB	Output is correct
13	Correct	149 ms	1640 KB	Output is correct
14	Correct	98 ms	1772 KB	Output is correct
15	Correct	640 ms	3532 KB	Output is correct
16	Correct	623 ms	3516 KB	Output is correct
17	Execution timed out	1174 ms	3552 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	584 KB	Output is correct
2	Correct	1 ms	584 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	584 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	5 ms	712 KB	Output is correct
7	Correct	13 ms	888 KB	Output is correct
8	Correct	37 ms	1096 KB	Output is correct
9	Correct	106 ms	1636 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	57 ms	1436 KB	Output is correct
12	Correct	112 ms	1760 KB	Output is correct
13	Correct	149 ms	1640 KB	Output is correct
14	Correct	98 ms	1772 KB	Output is correct
15	Correct	640 ms	3532 KB	Output is correct
16	Correct	623 ms	3516 KB	Output is correct
17	Execution timed out	1174 ms	3552 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	584 KB	Output is correct
2	Correct	1 ms	584 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	584 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	5 ms	712 KB	Output is correct
7	Correct	13 ms	888 KB	Output is correct
8	Correct	37 ms	1096 KB	Output is correct
9	Correct	106 ms	1636 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	57 ms	1436 KB	Output is correct
12	Correct	112 ms	1760 KB	Output is correct
13	Correct	149 ms	1640 KB	Output is correct
14	Correct	98 ms	1772 KB	Output is correct
15	Correct	640 ms	3532 KB	Output is correct
16	Correct	623 ms	3516 KB	Output is correct
17	Execution timed out	1174 ms	3552 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	584 KB	Output is correct
2	Correct	1 ms	584 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	584 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	5 ms	712 KB	Output is correct
7	Correct	13 ms	888 KB	Output is correct
8	Correct	37 ms	1096 KB	Output is correct
9	Correct	106 ms	1636 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	57 ms	1436 KB	Output is correct
12	Correct	112 ms	1760 KB	Output is correct
13	Correct	149 ms	1640 KB	Output is correct
14	Correct	98 ms	1772 KB	Output is correct
15	Correct	640 ms	3532 KB	Output is correct
16	Correct	623 ms	3516 KB	Output is correct
17	Execution timed out	1174 ms	3552 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	584 KB	Output is correct
2	Correct	1 ms	584 KB	Output is correct
3	Correct	1 ms	584 KB	Output is correct
4	Correct	1 ms	584 KB	Output is correct
5	Correct	2 ms	712 KB	Output is correct
6	Correct	5 ms	712 KB	Output is correct
7	Correct	13 ms	888 KB	Output is correct
8	Correct	37 ms	1096 KB	Output is correct
9	Correct	106 ms	1636 KB	Output is correct
10	Correct	2 ms	712 KB	Output is correct
11	Correct	57 ms	1436 KB	Output is correct
12	Correct	112 ms	1760 KB	Output is correct
13	Correct	149 ms	1640 KB	Output is correct
14	Correct	98 ms	1772 KB	Output is correct
15	Correct	640 ms	3532 KB	Output is correct
16	Correct	623 ms	3516 KB	Output is correct
17	Execution timed out	1174 ms	3552 KB	Time limit exceeded
18	Halted	0 ms	0 KB	-

답안 #486179

Compilation message