oj.uz

Submission #969065

# Submission time Handle Problem Language Result Execution time Memory
969065 2024-04-24T13:01:16 Z CyberCow A Difficult(y) Choice (BOI21_books) C++17
20 / 100
 158 ms 3612 KB 
#include "books.h"
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>

using namespace std;
using ll = long long;
const int N = 100010;
long long v[N];

void solve(int n, int k, long long a, int s) {

    if (n == s)
    {
        set<pair<long long, int>> se;
        for (int i = 1; i <= n; i++)
        {
            v[i] = skim(i);
            se.insert({ v[i], i });
        }
        int st = 0;
        ll sum = 0;
        for (int i = 1; i <= k; i++)
        {
            sum += v[i];
        }
        for (int i = k; i <= n; i++)
        {
            if (sum >= a && sum <= 2 * a)
            {
                vector<int> ans;
                for (int j = i - k + 1; j <= i; j++)
                {
                    ans.push_back(j);
                }
                answer(ans);
                return;
            }
            sum += v[i + 1] - v[i - k + 1];
        }
        sum = 0;
        for (int i = 1; i <= k - 1; i++)
        {
            sum += v[i];
        }
        for (int i = k; i <= n; i++)
        {
            if (sum + v[i] >= a && sum + v[i] <= 2 * a)
            {
                vector<int> ans;
                for (int j = 1; j < k; j++)
                {
                    ans.push_back(j);
                }
                ans.push_back(i);
                answer(ans);
                return;
            }
        }
        impossible();
    }
    set<pair<long long, int>> se;
    for (int i = 1; i <= n; i++)
    {
        v[i] = skim(i);
        se.insert({ v[i], i });
    }
    int st = 0;
    ll sum = 0;
    for (int i = 1; i <= k - 1; i++)
    {
        sum += v[i];
    }
    int l = k, r = n, m = 0, ans;
    while (l <= r)
    {
        m = (l + r) / 2;
        int x = skim(m);
        if (sum + x <= 2 * a && sum + x >= a)
        {
            vector<int> ans;
            for (int j = 1; j < k; j++)
            {
                ans.push_back(j);
            }
            ans.push_back(m);
            answer(ans);
            return;
        }
        else if(sum + x > 2 * a)
        {
            r = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }
    l = 1, r = n - k + 1, m = 0, ans;
    while (l <= r)
    {
        m = (l + r) / 2;
        sum = 0;
        for (int i = m; i < m + k; i++)
        {
            sum += skim(i);
        }
        if (sum > 2 * a)
        {
            r = m - 1;
        }
        else if (sum < a)
        {
            l = m + 1;
        }
        else
        {
            vector<int> ans;
            for (int j = m; j < m + k; j++)
            {
                ans.push_back(j);
            }
            answer(ans);
            return;
        }
    }
    impossible();
}

Compilation message

books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:23:13: warning: unused variable 'st' [-Wunused-variable]
   23 |         int st = 0;
      |             ^~
books.cpp:101:37: warning: right operand of comma operator has no effect [-Wunused-value]
  101 |     l = 1, r = n - k + 1, m = 0, ans;
      |                                     ^
books.cpp:70:9: warning: unused variable 'st' [-Wunused-variable]
   70 |     int st = 0;
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 6 ms 980 KB Output is correct
3 Correct 5 ms 972 KB Output is correct
4 Correct 5 ms 1000 KB Output is correct
5 Correct 4 ms 748 KB Output is correct
6 Correct 4 ms 744 KB Output is correct
7 Correct 4 ms 740 KB Output is correct
8 Correct 4 ms 708 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 688 KB Output is correct
2 Correct 4 ms 736 KB Output is correct
3 Correct 5 ms 708 KB Output is correct
4 Correct 4 ms 744 KB Output is correct
5 Correct 5 ms 736 KB Output is correct
6 Correct 5 ms 668 KB Output is correct
7 Correct 6 ms 700 KB Output is correct
8 Correct 4 ms 736 KB Output is correct
9 Correct 121 ms 2572 KB Output is correct
10 Correct 134 ms 2852 KB Output is correct
11 Correct 114 ms 2996 KB Output is correct
12 Correct 117 ms 2588 KB Output is correct
13 Correct 133 ms 3612 KB Output is correct
14 Correct 158 ms 2436 KB Output is correct
15 Correct 109 ms 2880 KB Output is correct
16 Correct 145 ms 3296 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 440 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -