답안 #963515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963515 2024-04-15T08:04:29 Z 12345678 도서관 (JOI18_library) C++17
100 / 100
224 ms 716 KB
#include <bits/stdc++.h>
#include "library.h"
using namespace std;

const int nx=1005;
int n, s=1;
vector<pair<int, int>> edg;
vector<int> v[nx], res;

int query(int l, int r)
{
    vector<int> qrs(n);
    for (int i=l; i<=r; i++) qrs[i-1]=1;
    int cnt=0;
    for (auto [x, y]:edg) if (l<=x&&y<=r) cnt++;
    return Query(qrs)+cnt;
}

void find_edge()
{
    int l=1, r=n;
    /*
    cout<<"test query : ";
    for (int i=1; i<=n; i++) cout<<query(1, i)<<' ';
    cout<<'\n'; */
    while (l<r)
    {
        int md=(l+r)/2;
        if (query(1, md)==md) l=md+1;
        else r=md;
    }
    int tmp=l;
    l=1, r=tmp;
    while (l<r)
    {
        int md=(l+r+1)/2;
        if (query(md, tmp)==tmp-md+1) r=md-1;
        else l=md;
    }
    edg.push_back({l, tmp});
    //cout<<"edge "<<l<<' '<<tmp<<'\n';
    //cout<<"debug "<<query(1, n)<<'\n';
}

void dfs(int u, int p)
{
	res.push_back(u);
	for (auto x:v[u]) if (x!=p) dfs(x, u);
}

void Solve(int N)
{
    n=N;
    //cout<<"test "<<query(1, n)<<'\n';
	for (int i=1; i<N; i++) find_edge();
    for (auto [x, y]:edg) v[x].push_back(y), v[y].push_back(x);
	for (int i=1; i<=N; i++) if (v[i].size()==1) s=i;
	dfs(s, s);
	Answer(res);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 460 KB # of queries: 2790
2 Correct 22 ms 456 KB # of queries: 2779
3 Correct 27 ms 596 KB # of queries: 2933
4 Correct 29 ms 464 KB # of queries: 2926
5 Correct 20 ms 456 KB # of queries: 2933
6 Correct 25 ms 456 KB # of queries: 2924
7 Correct 23 ms 600 KB # of queries: 2915
8 Correct 18 ms 456 KB # of queries: 2791
9 Correct 27 ms 460 KB # of queries: 2922
10 Correct 14 ms 460 KB # of queries: 1714
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 1 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 5
14 Correct 1 ms 344 KB # of queries: 11
15 Correct 1 ms 344 KB # of queries: 103
16 Correct 2 ms 344 KB # of queries: 232
# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 460 KB # of queries: 2790
2 Correct 22 ms 456 KB # of queries: 2779
3 Correct 27 ms 596 KB # of queries: 2933
4 Correct 29 ms 464 KB # of queries: 2926
5 Correct 20 ms 456 KB # of queries: 2933
6 Correct 25 ms 456 KB # of queries: 2924
7 Correct 23 ms 600 KB # of queries: 2915
8 Correct 18 ms 456 KB # of queries: 2791
9 Correct 27 ms 460 KB # of queries: 2922
10 Correct 14 ms 460 KB # of queries: 1714
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 1 ms 344 KB # of queries: 2
13 Correct 0 ms 344 KB # of queries: 5
14 Correct 1 ms 344 KB # of queries: 11
15 Correct 1 ms 344 KB # of queries: 103
16 Correct 2 ms 344 KB # of queries: 232
17 Correct 216 ms 464 KB # of queries: 19255
18 Correct 215 ms 464 KB # of queries: 19036
19 Correct 208 ms 464 KB # of queries: 19250
20 Correct 198 ms 468 KB # of queries: 18005
21 Correct 168 ms 460 KB # of queries: 16936
22 Correct 215 ms 464 KB # of queries: 19279
23 Correct 209 ms 704 KB # of queries: 19240
24 Correct 86 ms 444 KB # of queries: 8868
25 Correct 224 ms 456 KB # of queries: 18804
26 Correct 184 ms 460 KB # of queries: 17594
27 Correct 80 ms 456 KB # of queries: 8839
28 Correct 214 ms 464 KB # of queries: 18943
29 Correct 210 ms 460 KB # of queries: 18922
30 Correct 212 ms 716 KB # of queries: 18943