oj.uz

Submission #649440

# Submission time Handle Problem Language Result Execution time Memory
649440 2022-10-10T08:16:28 Z cadmiumsky A Difficult(y) Choice (BOI21_books) C++14
45 / 100
 2 ms 340 KB 
#include <bits/stdc++.h>

#include "books.h"

using namespace std;
using ll = long long;

const int nmax = 1e5 + 5;

namespace QUERY {
  ll v[nmax];
  set<int> ind;
  ll query(int x) {
    if(v[x] == 0) {
      v[x] = skim(x);
      ind.insert(x);
    }
    return v[x];
  }
}

ll n, k, a, s;

ll fmin(ll x) {
  return x * k + k * (k - 1) / 2;
}
ll fmax(ll x) {
  return x * k - k * (k - 1) / 2;
}
using namespace QUERY;
#define list shsflkhsdsdhsd
vector<ll> list;
vector<int> sol;
void mksolve(int lp, ll sum = 0) {
  if(sum > 2 * a) return;
  if(sol.size() == k) {
    if(sum >= a) {
      answer(sol);
    }
    return;
  }
  lp++;
  for(int i = lp; i + k - sol.size() <= list.size(); i++) {
    sol.push_back(list[i]);
    sum += v[list[i]];
    mksolve(i, sum);
    sol.pop_back();
    sum -= v[list[i]];
  }
  return;
}

void solve(int _N, int _K, long long _A, int _S) {
  n = _N;
  k = _K;
  a = _A;
  s = _S;
  s = min(40LL, s);
  int l = 0;
  for(int i = 16; i >= 0; i--) {
    if(l + (1 << i) >= n) continue;
    if(fmin(query(l + (1 << i))) < a)
      l += (1 << i);
    s--;
  }
  //cerr << l << ' ' << s << '\n';
  
  if(l == n)
    impossible();
  l++;
  s = min(s, 25LL);
  if(query(l) >= a) {
    list.push_back(l);
    for(int i = 1; i <= n && s > 0; s--, i++)
      query(i),
      list.push_back(i);
  }
  else {
    int lim = (s + 1) / 2;
    //cerr << lim << ' ' << s << '\n';
    for(int i = l; i > 0 && lim > 0; s--, i--, lim--)
      list.push_back(i),
      query(i);
    for(int i = max(1, l); s > 0 && i <= n; i++, s--)
      list.push_back(i),
      query(i);
  }
  sort(list.begin(), list.end());
  list.resize(unique(list.begin(), list.end()) - list.begin());
  //for(auto x : list) cerr << x << ' ';
  //cerr << '\n';
  sol.reserve(40);
  mksolve(-1);
  impossible();
}

Compilation message

books.cpp: In function 'void mksolve(int, ll)':
books.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   36 |   if(sol.size() == k) {
      |      ~~~~~~~~~~~^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Incorrect 1 ms 312 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Incorrect 1 ms 208 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 312 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 2 ms 312 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 1 ms 308 KB Output is correct
21 Correct 1 ms 304 KB Output is correct
22 Correct 1 ms 208 KB Output is correct
23 Correct 1 ms 312 KB Output is correct
24 Correct 1 ms 308 KB Output is correct
25 Correct 1 ms 308 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 2 ms 312 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 1 ms 308 KB Output is correct
21 Correct 1 ms 304 KB Output is correct
22 Correct 1 ms 208 KB Output is correct
23 Correct 1 ms 312 KB Output is correct
24 Correct 1 ms 308 KB Output is correct
25 Correct 1 ms 308 KB Output is correct
26 Correct 1 ms 316 KB Output is correct
27 Correct 1 ms 312 KB Output is correct
28 Correct 2 ms 292 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 312 KB Output is correct
33 Correct 1 ms 288 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 304 KB Output is correct
36 Correct 1 ms 304 KB Output is correct
37 Correct 1 ms 308 KB Output is correct
38 Correct 1 ms 244 KB Output is correct
39 Correct 1 ms 304 KB Output is correct
40 Correct 1 ms 208 KB Output is correct
41 Correct 1 ms 312 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 304 KB Output is correct
44 Correct 1 ms 300 KB Output is correct
45 Correct 1 ms 312 KB Output is correct
46 Correct 1 ms 308 KB Output is correct
47 Correct 1 ms 312 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Incorrect 1 ms 208 KB Incorrect
50 Halted 0 ms 0 KB -

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 2 ms 312 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 1 ms 308 KB Output is correct
21 Correct 1 ms 304 KB Output is correct
22 Correct 1 ms 208 KB Output is correct
23 Correct 1 ms 312 KB Output is correct
24 Correct 1 ms 308 KB Output is correct
25 Correct 1 ms 308 KB Output is correct
26 Correct 1 ms 304 KB Output is correct
27 Correct 1 ms 308 KB Output is correct
28 Correct 2 ms 312 KB Output is correct
29 Correct 1 ms 328 KB Output is correct
30 Correct 1 ms 312 KB Output is correct
31 Correct 1 ms 304 KB Output is correct
32 Correct 1 ms 316 KB Output is correct
33 Correct 1 ms 208 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 336 KB Output is correct
37 Correct 1 ms 308 KB Output is correct
38 Correct 1 ms 304 KB Output is correct
39 Correct 1 ms 312 KB Output is correct
40 Correct 1 ms 208 KB Output is correct
41 Correct 1 ms 312 KB Output is correct
42 Correct 1 ms 208 KB Output is correct
43 Correct 1 ms 312 KB Output is correct
44 Correct 1 ms 316 KB Output is correct
45 Correct 1 ms 336 KB Output is correct
46 Correct 1 ms 208 KB Output is correct
47 Correct 1 ms 312 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Correct 1 ms 308 KB Output is correct
50 Correct 1 ms 316 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 2 ms 312 KB Output is correct
13 Correct 1 ms 304 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 208 KB Output is correct
17 Correct 1 ms 288 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 1 ms 308 KB Output is correct
21 Correct 1 ms 304 KB Output is correct
22 Correct 1 ms 208 KB Output is correct
23 Correct 1 ms 312 KB Output is correct
24 Correct 1 ms 308 KB Output is correct
25 Correct 1 ms 308 KB Output is correct
26 Correct 1 ms 316 KB Output is correct
27 Correct 1 ms 312 KB Output is correct
28 Correct 2 ms 292 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 312 KB Output is correct
33 Correct 1 ms 288 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 304 KB Output is correct
36 Correct 1 ms 304 KB Output is correct
37 Correct 1 ms 308 KB Output is correct
38 Correct 1 ms 244 KB Output is correct
39 Correct 1 ms 304 KB Output is correct
40 Correct 1 ms 208 KB Output is correct
41 Correct 1 ms 312 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 304 KB Output is correct
44 Correct 1 ms 300 KB Output is correct
45 Correct 1 ms 312 KB Output is correct
46 Correct 1 ms 308 KB Output is correct
47 Correct 1 ms 312 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Incorrect 1 ms 208 KB Incorrect
50 Halted 0 ms 0 KB -