제출 #1256413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1256413		tvgk	도서관 (JOI18_library)	C++20	100 / 100	75 ms	476 KiB

library

#include <cstdio>
#include <vector>
#include "library.h"
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e3 + 7;

vector<int> w[mxN], ans;
int cnt[mxN], n;

int Ask(int u, int v)
{
    vector<int> vc(n, 0);
    int res = v - u + 1;
    for (int i = u; i <= v; i++)
    {
        vc[i - 1] = 1;
        res -= cnt[i];
    }

    return Query(vc) - res;
}

void DFS(int j, int par)
{
    ans.push_back(j);
    for (int i : w[j])
    {
        if (par == i)
            continue;
        DFS(i, j);
    }
}

void Solve(int N)
{
    n = N;
    for (int i = 1; i <= n; i++)
    {
        while (Ask(1, i))
        {
            int l = 1, r = i - 1, k = 1;
            while (l <= r)
            {
                int mid = (l + r) / 2;

                if (Ask(mid, i))
                {
                    k = mid;
                    l = mid + 1;
                }
                else
                    r = mid - 1;
            }

            cnt[k]++;
            w[k].push_back(i);
            w[i].push_back(k);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (w[i].size() <= 1)
        {
            DFS(i, -1);
            break;
        }
    }

	Answer(ans);
}

• Subtask 1: 19 / 19
• Subtask 2: 81 / 81