oj.uz

답안 #285058

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
285058 2020-08-28T09:36:52 Z Coroian_David 도서관 (JOI18_library) C++11
100 / 100
 354 ms 512 KB 
#include <bits/stdc++.h>

#define MAX_N 1000

//#include "library.h"

using namespace std;

int Query(const std::vector<int>& M);
void Answer(const std::vector<int>& res);

int n;
vector <int> tmp;
vector <int> rez;

int done[MAX_N + 1];

void divide(int st, int dr, int poz)
{
    //cout << " SUNTEM " << st << " " << dr << " " << poz << "\n";

    if(st == dr)
    {
        done[st - 1] = 1;
        rez[poz + 1] = st;

        return;
    }

    int mid = (dr + st) >> 1;

    int cate = 0;
    for(int i = st; i <= mid; i ++)
        tmp[i - 1] = 1 - done[i - 1], cate += tmp[i - 1];

    for(int i = mid + 1; i <= dr; i ++)
        tmp[i - 1] = 0;

    int x = 0, y = 1;
    if(cate != 0)
    {
        x = Query(tmp);
        tmp[rez[poz] - 1] = 1;
        y = Query(tmp);
    }

    for(int i = st; i <= dr; i ++)
        tmp[i - 1] = 0;
    tmp[rez[poz] - 1] = 0;

    y == x ? divide(st, mid, poz) : divide(mid + 1, dr, poz);
}

void Solve(int N)
{
    n = N;

    tmp.resize(N);
    rez.resize(N);
	for(int i = 0; i < n; i++)
		tmp[i] = 1;

    if(n == 1)
    {
        rez[0] = 1;
        Answer(rez);
        return;
    }

    for(int i = 0; i < n; i ++)
    {
        tmp[i] = 0;
        int x = Query(tmp);

        if(x == 1)
        {
            done[i] = 1;
            rez[0] = i + 1;
            break;
        }

        tmp[i] = 1;
    }

    //cout << rez[0] << "\n";

    for(int i = 1; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
            tmp[j] = 0;

        divide(1, n, i - 1);
    }

   /* for(int i = 0; i < n; i ++)
        cout << rez[i] << " ";
    cout << "\n";*/

	Answer(rez);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 256 KB # of queries: 2749
2 Correct 45 ms 256 KB # of queries: 2787
3 Correct 41 ms 256 KB # of queries: 3004
4 Correct 47 ms 256 KB # of queries: 2921
5 Correct 41 ms 256 KB # of queries: 2868
6 Correct 39 ms 256 KB # of queries: 2919
7 Correct 38 ms 256 KB # of queries: 2908
8 Correct 45 ms 256 KB # of queries: 2742
9 Correct 29 ms 256 KB # of queries: 2880
10 Correct 23 ms 256 KB # of queries: 1628
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 1
13 Correct 0 ms 256 KB # of queries: 6
14 Correct 0 ms 256 KB # of queries: 7
15 Correct 2 ms 256 KB # of queries: 91
16 Correct 5 ms 256 KB # of queries: 231

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 256 KB # of queries: 2749
2 Correct 45 ms 256 KB # of queries: 2787
3 Correct 41 ms 256 KB # of queries: 3004
4 Correct 47 ms 256 KB # of queries: 2921
5 Correct 41 ms 256 KB # of queries: 2868
6 Correct 39 ms 256 KB # of queries: 2919
7 Correct 38 ms 256 KB # of queries: 2908
8 Correct 45 ms 256 KB # of queries: 2742
9 Correct 29 ms 256 KB # of queries: 2880
10 Correct 23 ms 256 KB # of queries: 1628
11 Correct 0 ms 256 KB # of queries: 0
12 Correct 0 ms 256 KB # of queries: 1
13 Correct 0 ms 256 KB # of queries: 6
14 Correct 0 ms 256 KB # of queries: 7
15 Correct 2 ms 256 KB # of queries: 91
16 Correct 5 ms 256 KB # of queries: 231
17 Correct 354 ms 256 KB # of queries: 19548
18 Correct 335 ms 256 KB # of queries: 18781
19 Correct 322 ms 384 KB # of queries: 18931
20 Correct 270 ms 384 KB # of queries: 17933
21 Correct 268 ms 512 KB # of queries: 16904
22 Correct 335 ms 384 KB # of queries: 19157
23 Correct 310 ms 384 KB # of queries: 18738
24 Correct 130 ms 256 KB # of queries: 8615
25 Correct 307 ms 384 KB # of queries: 18634
26 Correct 302 ms 384 KB # of queries: 17475
27 Correct 138 ms 256 KB # of queries: 8856
28 Correct 167 ms 384 KB # of queries: 10069
29 Correct 174 ms 384 KB # of queries: 10063
30 Correct 177 ms 384 KB # of queries: 10069