oj.uz

답안 #768630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768630 2023-06-28T10:13:34 Z raysh07 도서관 (JOI18_library) C++17
19 / 100
 177 ms 340 KB 
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
vector<vector<int>> adj;
vector<int> comp;
vector<bool> vis;
vector<int> m;

void init(int n){
    for (int i = 0; i < n; i++) m[i] = 0;
}

bool check(int i, int j, int n){
    if (i == j) return false;
    
    for (int k = i; k <= j; k++){
        m[k] = 1;
    }
    int cnt = 0;
    
    for (auto x : adj[i]) m[x] = 0;
    
    for (int i = 0; i < n; i++) cnt += m[i];
    
    if (cnt == 1) {
        init(n);
        return false;
    }
    
    int a1 = Query(m);
    m[i] = 0;
    int a2;
    if (cnt != 2)
    a2 = Query(m);
    else a2 = 1;
    
    init(n);
    return a2 >= a1;
}

void dfs(int u, int par = -1){
    comp.push_back(u + 1);
    vis[u] = true;
    for (int v : adj[u]){
        if (v != par){
            assert(!vis[v]);
            dfs(v, u);
        }
    }
}

void Solve(int n)
{
// 	vector<int> M(N);

// 	for(int i = 0; i < N; i++) {
// 		M[i] = 1;
// 	}

// 	int A = Query(M);

// 	vector<int> res(N);

// 	for(int i = 0; i < N; i++) {
// 		res[i] = i + 1;
// 	}

// 	Answer(res);

    if (n == 1){
        Answer({1});
        return;
    }
    if (n == 2){
        Answer({1, 2});
        return;
    }
    
    m.resize(n, 0);
    adj.resize(n);
    vis.resize(n, false);
    
    int ok = 0;

    for (int i = 0; i < n; i++){
        while (adj[i].size() < 2 && check(i, n - 1, n)){
            int l = i + 1, r = n - 1;
            
            while (l != r){
                int m = (l + r)/2;
                
                if (check(i, m, n)) r = m;
                else l = m + 1;
            }
            
            ok++;
            adj[i].push_back(l);
            adj[l].push_back(i);
        }
    }
    
  //  assert(ok == n - 1);
    int holy = 0;
    for (int i = 0; i < n; i++) {
        holy += adj[i].size();
     //   assert(adj[i].size() >= 1);
    }
    
  //  assert(holy == 2 * n - 2);
    
    for (int i = 0; i < n; i++){
        if (adj[i].size() == 1){
            dfs(i);
            break;
        }
    }
  //  assert(comp.size() == n);
    
    Answer(comp);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 208 KB # of queries: 3020
2 Correct 27 ms 284 KB # of queries: 2997
3 Correct 35 ms 300 KB # of queries: 3182
4 Correct 33 ms 292 KB # of queries: 3159
5 Correct 33 ms 208 KB # of queries: 3170
6 Correct 29 ms 300 KB # of queries: 3186
7 Correct 26 ms 292 KB # of queries: 3178
8 Correct 28 ms 208 KB # of queries: 3031
9 Correct 34 ms 208 KB # of queries: 3140
10 Correct 23 ms 304 KB # of queries: 1874
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 0 ms 208 KB # of queries: 5
14 Correct 0 ms 208 KB # of queries: 11
15 Correct 2 ms 208 KB # of queries: 117
16 Correct 3 ms 296 KB # of queries: 267

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 208 KB # of queries: 3020
2 Correct 27 ms 284 KB # of queries: 2997
3 Correct 35 ms 300 KB # of queries: 3182
4 Correct 33 ms 292 KB # of queries: 3159
5 Correct 33 ms 208 KB # of queries: 3170
6 Correct 29 ms 300 KB # of queries: 3186
7 Correct 26 ms 292 KB # of queries: 3178
8 Correct 28 ms 208 KB # of queries: 3031
9 Correct 34 ms 208 KB # of queries: 3140
10 Correct 23 ms 304 KB # of queries: 1874
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 0
13 Correct 0 ms 208 KB # of queries: 5
14 Correct 0 ms 208 KB # of queries: 11
15 Correct 2 ms 208 KB # of queries: 117
16 Correct 3 ms 296 KB # of queries: 267
17 Runtime error 177 ms 340 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -