Submission #522922

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
522922	2022-02-06 12:59:32	qwerasdfzxcl	Park (JOI17_park)	C++14	100 / 100	472 ms	768 KiB

park

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "park.h"
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
static int Place[1400];
int a[1400], Qcnt;
 
int ask(int x, int y){assert(++Qcnt<=35000); return Ask(min(x, y), max(x, y), Place);}
void answer(int x, int y){Answer(min(x, y), max(x, y));}
 
void _sort(int n){
    vector<int> ans = {0};
 
    for (int i=1;i<n;i++){
        fill(Place, Place+1400, 1);
 
        int l = 1, r = (int)ans.size()-1, idx = 0;
        while(l<=r){
            int m = (l+r)>>1;
            for (int j=0;j<m;j++) Place[ans[j]] = 1;
            for (int j=m;j<(int)ans.size();j++) Place[ans[j]] = 0;
 
            if (ask(0, i)) r = m-1;
            else l = m+1, idx = m;
        }
        ans.insert(ans.begin()+idx+1, i);
    }
    for (int i=0;i<n;i++) a[i] = ans[i];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23