Submission #1067285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067285		duckindog	A Difficult(y) Choice (BOI21_books)	C++17	60 / 100	1000 ms	2152 KiB

books

#include <bits/stdc++.h>
 
#include "books.h"
 
using namespace std;

namespace sub5 { 
  void solve(int n, int k, long long a, int s) { 
    vector<long long> x(n + 1);
    vector<int> ret;
    { // k - 1
      long long total = 0;
      for (int i = 1; i < k; ++i) { 
        if (!x[i]) x[i] = skim(i);
        total += x[i];
      }
  
      auto get = [&](int i) { 
        if (!x[i]) x[i] = skim(i);
        return total + x[i];
      };
  
      int l = k, r = n;
      while (l <= r) { 
        int mid = l + r >> 1;
  
        auto value = get(mid);
        if (a <= value && value <= 2 * a) { 
          for (int i = 1; i < k; ++i) ret.push_back(i);
          ret.push_back(mid);
          answer(ret);
          return;
        }
  
        if (value < a) l = mid + 1;
        else r = mid - 1;
      }
    }
  
    { //consecutive
      auto get = [&](int l, int r) { 
        long long total = 0;
        for (int i = l; i <= r; ++i) {
          if (!x[i]) x[i] = skim(i);
          total += x[i];
        }
        return total;
      };
  
      int l = k, r = n;
      while (l <= r) { 
        int mid = l + r >> 1;
  
        auto value = get(mid - k + 1, mid);
        if (a <= value && value <= 2 * a) { 
          for (int i = mid - k + 1; i <= mid; ++i) ret.push_back(i);
          answer(ret);
          return;
        }
  
        if (value < a) l = mid + 1;
        else r = mid - 1;
      }
    }
    impossible();
  }
}

void solve(int n, int k, long long a, int s) {
  if (s >= 170) { sub5::solve(n, k, a, s); return; }

  vector<long long> x(n + 1);
  vector<bool> mk(n + 1);
  long long total = 0, cnt = k;
  for (int i = 1; i <= k; ++i) { 
    if (!x[i]) x[i] = skim(i);
    mk[i] = true;
    total += x[i];
  }

  auto done = [&]() { 
    vector<int> ret;
    if (a <= total && total <= 2 * a) { 
      for (int i = 1; i <= n; ++i) if (mk[i]) ret.push_back(i);
      answer(ret);
      exit(0);
    }
  };
  
  for (;;) { 
    done();
    vector<int> pool;
    for (int i = 1; i <= n; ++i) if (!mk[i]) pool.push_back(i);
    if (!pool.size()) break;

    for (int i = 1; i <= n; ++i) { 
      if (mk[i]) { 
        total -= x[i];
        mk[i] = false;
        break;
      }
    }

    int l = 0, r = pool.size() - 1;
    while (l <= r) { 
      if (cnt == min(s, n) || 1.0 * clock() / CLOCKS_PER_SEC > 1) break;
      int mid = l + r >> 1;

      if (!x[pool[mid]]) {
        x[pool[mid]] = skim(pool[mid]);
        cnt += 1;
      }
      mk[pool[mid]] = true;
      done();
      mk[pool[mid]] = false;

      if (total + x[pool[mid]] <= 2 * a) l = mid + 1;
      else r = mid - 1;
    }
    if (cnt == min(s, n) || 1.0 * clock() / CLOCKS_PER_SEC > 1) break;
  }

  impossible();
}

Compilation message (stderr)

books.cpp: In function 'void sub5::solve(int, int, long long int, int)':
books.cpp:25:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |         int mid = l + r >> 1;
      |                   ~~^~~
books.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = l + r >> 1;
      |                   ~~^~~
books.cpp: In function 'void solve(int, int, long long int, int)':
books.cpp:107:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |       int mid = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20