# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
529198 | 2022-02-22T11:39:30 Z | Cross_Ratio | A Difficult(y) Choice (BOI21_books) | C++14 | 2 ms | 968 KB |
#include <bits/stdc++.h> //#include "books.h" using namespace std; typedef long long ll; ll D[100005]; ll skim(int); void answer(vector<int>); void impossible(); int cnt = 0; ll get(int m) { if(D[m]!=-1) return D[m]; assert(cnt<40); D[m] = skim(m+1); cnt++; return D[m]; } void solve(int N, int K, ll A, int S) { int i, j, a, b; for(i=0;i<N;i++) D[i] = -1; ll sum = 0; for(i=0;i<K-1;i++) sum += get(i); if(sum >= A) { impossible(); return; } int s = K-2, e = N-1; while(s+1<e) { int mid = (s + e + 1) >> 1; if(get(mid)>=A-sum) e = mid; else s = mid; } if(get(e)>=A-sum) { if(get(e)<=2*A-sum) { vector<int> ans; for(i=1;i<=K-1;i++) ans.push_back(i); ans.push_back(e+1); answer(ans); return; } N = e; } if(N < K) { impossible(); return; } for(i=0;i<=K;i++) { vector<int> ans; for(j=1;j<=i;j++) ans.push_back(j); for(j=N-K+1+i;j<=N;j++) ans.push_back(j); sort(ans.begin(),ans.end()); ans.erase(unique(ans.begin(),ans.end()),ans.end()); if(ans.size() != K) continue; ll sum = 0; for(int m=0;m<ans.size();m++) { sum += get(ans[m]-1); } if(sum >= A && sum <= 2*A) { answer(ans); return; } } impossible(); return; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 200 KB | Output is correct |
2 | Correct | 1 ms | 200 KB | Output is correct |
3 | Correct | 0 ms | 200 KB | Output is correct |
4 | Correct | 1 ms | 200 KB | Output is correct |
5 | Correct | 0 ms | 200 KB | Output is correct |
6 | Correct | 1 ms | 200 KB | Output is correct |
7 | Correct | 1 ms | 200 KB | Output is correct |
8 | Correct | 0 ms | 200 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 200 KB | Output is correct |
2 | Correct | 1 ms | 200 KB | Output is correct |
3 | Correct | 1 ms | 200 KB | Output is correct |
4 | Correct | 1 ms | 200 KB | Output is correct |
5 | Correct | 1 ms | 200 KB | Output is correct |
6 | Correct | 1 ms | 200 KB | Output is correct |
7 | Correct | 1 ms | 200 KB | Output is correct |
8 | Correct | 1 ms | 200 KB | Output is correct |
9 | Correct | 1 ms | 416 KB | Output is correct |
10 | Correct | 1 ms | 456 KB | Output is correct |
11 | Correct | 1 ms | 456 KB | Output is correct |
12 | Correct | 1 ms | 456 KB | Output is correct |
13 | Incorrect | 1 ms | 456 KB | Incorrect |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 968 KB | Output is correct |
2 | Correct | 1 ms | 968 KB | Output is correct |
3 | Correct | 1 ms | 968 KB | Output is correct |
4 | Correct | 2 ms | 968 KB | Output is correct |
5 | Correct | 1 ms | 968 KB | Output is correct |
6 | Correct | 1 ms | 968 KB | Output is correct |
7 | Correct | 1 ms | 968 KB | Output is correct |
8 | Correct | 1 ms | 968 KB | Output is correct |
9 | Incorrect | 1 ms | 968 KB | Incorrect |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 968 KB | Output is correct |
2 | Correct | 1 ms | 968 KB | Output is correct |
3 | Correct | 1 ms | 968 KB | Output is correct |
4 | Correct | 2 ms | 968 KB | Output is correct |
5 | Correct | 1 ms | 968 KB | Output is correct |
6 | Correct | 1 ms | 968 KB | Output is correct |
7 | Correct | 1 ms | 968 KB | Output is correct |
8 | Correct | 1 ms | 968 KB | Output is correct |
9 | Incorrect | 1 ms | 968 KB | Incorrect |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 968 KB | Output is correct |
2 | Correct | 1 ms | 968 KB | Output is correct |
3 | Correct | 1 ms | 968 KB | Output is correct |
4 | Correct | 2 ms | 968 KB | Output is correct |
5 | Correct | 1 ms | 968 KB | Output is correct |
6 | Correct | 1 ms | 968 KB | Output is correct |
7 | Correct | 1 ms | 968 KB | Output is correct |
8 | Correct | 1 ms | 968 KB | Output is correct |
9 | Incorrect | 1 ms | 968 KB | Incorrect |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 968 KB | Output is correct |
2 | Correct | 1 ms | 968 KB | Output is correct |
3 | Correct | 1 ms | 968 KB | Output is correct |
4 | Correct | 2 ms | 968 KB | Output is correct |
5 | Correct | 1 ms | 968 KB | Output is correct |
6 | Correct | 1 ms | 968 KB | Output is correct |
7 | Correct | 1 ms | 968 KB | Output is correct |
8 | Correct | 1 ms | 968 KB | Output is correct |
9 | Incorrect | 1 ms | 968 KB | Incorrect |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 968 KB | Output is correct |
2 | Correct | 1 ms | 968 KB | Output is correct |
3 | Correct | 1 ms | 968 KB | Output is correct |
4 | Correct | 2 ms | 968 KB | Output is correct |
5 | Correct | 1 ms | 968 KB | Output is correct |
6 | Correct | 1 ms | 968 KB | Output is correct |
7 | Correct | 1 ms | 968 KB | Output is correct |
8 | Correct | 1 ms | 968 KB | Output is correct |
9 | Incorrect | 1 ms | 968 KB | Incorrect |
10 | Halted | 0 ms | 0 KB | - |