oj.uz

답안 #617587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
617587 2022-08-01T12:18:32 Z Ahmadsm2005 도서관 (JOI18_library) C++17
100 / 100
 909 ms 1452 KB 
#include <bits/stdc++.h>
#include "library.h"
//#include "grader.cpp"
using namespace std;
bool E[1000][1000],VIS[1000];
int CNT[1000],NN;
void DFS(int v,int L,int R,int BL){
    if(VIS[v])return;
    VIS[v] = 1;
    for(int i = 0; i < NN; i += 1)if(E[i][v] && i >= L && i <= R && i != BL)DFS(i,L,R,BL);
}
int BS(int idx,int BL = -1){
    int L = 0, R = idx - 1 -(BL != -1), mid;
    while(L <= R){
        if(L == R){
            E[idx][L + (L >= BL && BL != -1)] = E[L + (L >= BL && BL != -1)][idx] = 1;
            CNT[idx]++,CNT[L + (L >= BL && BL != -1)]++;
            //cout<<L + 1 + (L >= BL && BL != -1)<<endl;
            return L + (L >= BL && BL != -1);
        }
        //cout<<L<<' '<<R<<endl;
        vector<int>F(NN,0);
        mid = (L + R) / 2;
        int Z = 0;
        for(int i = L; i <= mid; i += 1)F[i + (BL != -1 && i >= BL)] = 1;
        F[idx] = 1;
        for(int i = L; i <= mid; i += 1){
            //cout<<"Q: " <<i + (BL != -1 && i >= BL)<<endl;
            if(!VIS[i + (BL != -1 && i >= BL)])DFS(i + (BL != -1 && i >= BL),L + (BL != -1 && L >= BL),mid + (BL != -1 && mid >= BL),BL),Z++;
        }
        //cout<<"Z: "<<Z<<' '<<Query(F)<<endl;
        if(Z >= Query(F))R = mid;
        else L = mid + 1;
        for(int i = 0; i < NN; i += 1)VIS[i] = 0;
    }
}
void Solve(int N)
{
    NN = N;
	vector<int> M(N);
    M[0] = 1;
    int LST = 1;
	for(int i = 1; i < N; i += 1){
        M[i] = 1;
        int A = Query(M);
        if(A <= LST){
            //cout<<"Hmm: "<<i + 1<<endl;
            if(A == LST)BS(i);
            else{
                int Q = BS(i);
                //cout<<"BL: "<<Q<<endl;
                BS(i,Q);
            }
        }
        LST = A;
	}
	int S = 0, P = -1;
	for(int i = 0; i < N; i += 1)if(CNT[i] == 1){S = i;}
	vector<int> res;
	while(1){
        res.push_back(S + 1);
        //cout<<S + 1<<' ';
        for(int i = 0; i < N; i += 1)if(i != P && E[S][i]){P = S, S = i; goto a;}
        break;
        a:;
	}
	//cout<<res.size()<<endl;
	Answer(res);
}

Compilation message

library.cpp: In function 'int BS(int, int)':
library.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
   36 | }
      | ^

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 464 KB # of queries: 1520
2 Correct 28 ms 468 KB # of queries: 1504
3 Correct 37 ms 404 KB # of queries: 1585
4 Correct 29 ms 492 KB # of queries: 1583
5 Correct 36 ms 484 KB # of queries: 1580
6 Correct 32 ms 576 KB # of queries: 1587
7 Correct 19 ms 468 KB # of queries: 1595
8 Correct 27 ms 476 KB # of queries: 1509
9 Correct 28 ms 432 KB # of queries: 1593
10 Correct 20 ms 392 KB # of queries: 939
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 1
13 Correct 0 ms 308 KB # of queries: 3
14 Correct 1 ms 208 KB # of queries: 6
15 Correct 1 ms 208 KB # of queries: 57
16 Correct 3 ms 208 KB # of queries: 130

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 464 KB # of queries: 1520
2 Correct 28 ms 468 KB # of queries: 1504
3 Correct 37 ms 404 KB # of queries: 1585
4 Correct 29 ms 492 KB # of queries: 1583
5 Correct 36 ms 484 KB # of queries: 1580
6 Correct 32 ms 576 KB # of queries: 1587
7 Correct 19 ms 468 KB # of queries: 1595
8 Correct 27 ms 476 KB # of queries: 1509
9 Correct 28 ms 432 KB # of queries: 1593
10 Correct 20 ms 392 KB # of queries: 939
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 1 ms 208 KB # of queries: 1
13 Correct 0 ms 308 KB # of queries: 3
14 Correct 1 ms 208 KB # of queries: 6
15 Correct 1 ms 208 KB # of queries: 57
16 Correct 3 ms 208 KB # of queries: 130
17 Correct 909 ms 1452 KB # of queries: 10293
18 Correct 819 ms 1260 KB # of queries: 10157
19 Correct 876 ms 1368 KB # of queries: 10273
20 Correct 712 ms 1204 KB # of queries: 9627
21 Correct 666 ms 1272 KB # of queries: 9026
22 Correct 858 ms 1320 KB # of queries: 10318
23 Correct 789 ms 1276 KB # of queries: 10264
24 Correct 175 ms 804 KB # of queries: 4775
25 Correct 770 ms 1360 KB # of queries: 10070
26 Correct 670 ms 1204 KB # of queries: 9420
27 Correct 148 ms 704 KB # of queries: 4770
28 Correct 735 ms 1276 KB # of queries: 8977
29 Correct 731 ms 1380 KB # of queries: 8967
30 Correct 713 ms 1332 KB # of queries: 8977