# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
529200 | 2022-02-22T11:46:32 Z | Cross_Ratio | A Difficult(y) Choice (BOI21_books) | C++14 | 1 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(); assert(0); return; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 200 KB | Output is correct |
2 | Correct | 0 ms | 200 KB | Output is correct |
3 | Correct | 1 ms | 200 KB | Output is correct |
4 | Correct | 0 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 | 0 ms | 200 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 200 KB | Output is correct |
2 | Correct | 1 ms | 200 KB | Output is correct |
3 | Correct | 1 ms | 244 KB | Output is correct |
4 | Correct | 1 ms | 200 KB | Output is correct |
5 | Correct | 1 ms | 200 KB | Output is correct |
6 | Correct | 0 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 | 456 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 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 | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 1 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 | - |