#409127 (C++17) No.953 席

提出ソース
結果

問題	No.953 席
ユーザー	👑 emthrm
提出日時	2019-12-16 10:36:49
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	13,733 bytes
コンパイル時間	2,435 ms
コンパイル使用メモリ	159,436 KB
実行使用メモリ	9,812 KB
最終ジャッジ日時	2023-09-15 17:26:00
合計ジャッジ時間	7,245 ms
ジャッジサーバーID （参考情報）	judge12 / judge14
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	99 ms 4,376 KB
testcase_03	AC	96 ms 4,376 KB
testcase_04	AC	98 ms 4,376 KB
testcase_05	AC	88 ms 4,376 KB
testcase_06	AC	99 ms 4,376 KB
testcase_07	AC	135 ms 9,060 KB
testcase_08	AC	142 ms 8,920 KB
testcase_09	AC	114 ms 9,600 KB
testcase_10	AC	38 ms 5,212 KB
testcase_11	AC	103 ms 6,804 KB
testcase_12	AC	118 ms 6,520 KB
testcase_13	AC	140 ms 8,872 KB
testcase_14	AC	115 ms 6,116 KB
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	AC	106 ms 4,932 KB
testcase_24	WA	-
testcase_25	AC	143 ms 9,132 KB
testcase_26	AC	71 ms 4,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
// const int dy[] = {1, 1, 0, -1, -1, -1, 0, 1},
//           dx[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cerr << fixed << setprecision(10);
  }
} iosetup;
/*-------------------------------------------------*/
const int lg10_base = 9, base = static_cast<int>(round(pow(10, lg10_base)));
struct BigInt {
  int sign;
  vector<int> dat;
  BigInt(long long val = 0) { *this = val; }
  BigInt(const string &str) { *this = str; }
  vector<long long> convert_base(int new_lg10_base, long long new_base) const {
    // assert(new_base == static_cast<int>(round(pow(10, new_lg10_base))))
    int mx_base = max(lg10_base, new_lg10_base);
    vector<long long> p(mx_base + 1, 1);
    FOR(i, 1, mx_base + 1) p[i] = p[i - 1] * 10;
    vector<long long> res;
    long long now_val = 0;
    int now_lg10_base = 0;
    for (int e : dat) {
      now_val += p[now_lg10_base] * e;
      now_lg10_base += lg10_base;
      while (now_lg10_base >= new_lg10_base) {
        res.emplace_back(now_val % new_base);
        now_val /= new_base;
        now_lg10_base -= new_lg10_base;
      }
    }
    res.emplace_back(now_val);
    while (!res.empty() && res.back() == 0) res.pop_back();
    return res;
  }
  int digit_sum() {
    assert(sign == 1);
    string str = to_string();
    int res = 0;
    for (char c : str) res += c - '0';
    return res;
  }
  int length() {
    if (dat.empty()) return 1;
    int res = lg10_base * (dat.size() - 1);
    int tmp = dat.back();
    while (tmp > 0) { ++res; tmp /= 10; }
    return res;
  }
  BigInt pow(BigInt exponent) {
    BigInt res = 1, tmp = *this;
    while (exponent > 0) {
      if (exponent.dat[0] & 1) res *= tmp;
      tmp *= tmp;
      exponent /= 2;
    }
    return res;
  }
  long long to_llong() const {
    assert(*this >= INT64_MIN && *this <= INT64_MAX);
    long long res = 0;
    for (int i = static_cast<int>(dat.size()) - 1; i >= 0; --i) (res *= base) += dat[i];
    return res;
  }
  string to_string() { stringstream ss; ss << *this; string res; ss >> res; return res; }
  void trim() {
    while (!dat.empty() && dat.back() == 0) dat.pop_back();
    if (dat.empty()) sign = 1;
  }
  BigInt &operator=(long long val) {
    sign = 1;
    if (val < 0) { sign = -1; val *= -1;}
    dat.clear();
    for (; val > 0; val /= base) dat.emplace_back(val % base);
    return *this;
  }
  BigInt &operator=(const string &str) {
    sign = 1;
    dat.clear();
    if (!str.empty()) {
      int tail = 0;
      if (str[tail] == '-' || str[tail] == '+') {
        if (str[tail] == '-') sign = -1;
        ++tail;
      }
      for (int i = str.length() - 1; i >= tail; i -= lg10_base) {
        int val = 0;
        for (int j = max(tail, i - lg10_base + 1); j <= i; ++j) val = val * 10 + (str[j] - '0');
        dat.emplace_back(val);
      }
    }
    trim();
    return *this;
  }
  BigInt &operator=(const BigInt &rhs) {
    sign = rhs.sign;
    dat.resize(rhs.dat.size());
    copy(ALL(rhs.dat), dat.begin());
    return *this;
  }
  BigInt &operator+=(const BigInt &rhs) {
    if (sign == rhs.sign) {
      bool carry = false;
      for (int i = 0; i < max(dat.size(), rhs.dat.size()) || carry; ++i) {
        if (i == dat.size()) dat.emplace_back(0);
        dat[i] += (i < rhs.dat.size() ? rhs.dat[i] : 0) + carry;
        carry = dat[i] >= base;
        if (carry) dat[i] -= base;
      }
    } else {
      *this -= -rhs;
    }
    return *this;
  }
  BigInt &operator-=(const BigInt &rhs) {
    if (sign == rhs.sign) {
      BigInt abs_lhs = *this, abs_rhs = rhs;
      abs_lhs.sign = 1; abs_rhs.sign = 1;
      if (abs_lhs >= abs_rhs) {
        bool carry = false;
        for (int i = 0; i < dat.size() || carry; ++i) {
          dat[i] -= (i < rhs.dat.size() ? rhs.dat[i] : 0) + carry;
          carry = dat[i] < 0;
          if (carry) dat[i] += base;
        }
        trim();
      } else {
        *this = -(rhs - *this);
      }
    } else {
      *this += -rhs;
    }
    return *this;
  }
  BigInt &operator*=(const BigInt &rhs) {
    const int new_log10_base = 6, new_base = 1000000;
    vector<long long> lhs6 = convert_base(new_log10_base, new_base), rhs6 = rhs.convert_base(new_log10_base, new_base);
    vector<long long> res = karatsuba(lhs6, 0, lhs6.size(), rhs6, 0, rhs6.size());
    REP(i, res.size()) {
      long long quo = res[i] / new_base;
      if (quo > 0) {
        if (i + 1 == res.size()) res.emplace_back(0);
        res[i + 1] += quo;
      }
      res[i] %= new_base;
    }
    string str = (sign * rhs.sign == 1 ? "+" : "-");
    for (int i = static_cast<int>(res.size()) - 1; i >= 0; --i) {
      string tmp = std::to_string(res[i]);
      REP(_, new_log10_base - tmp.size()) str += '0';
      str += tmp;
    }
    return *this = str;
  }
  BigInt &operator/=(int rhs) { return *this = divide(rhs).first; }
  BigInt &operator/=(const BigInt &rhs) { return *this = divide(rhs).first; }
  BigInt &operator%=(int rhs) { return *this = divide(rhs).second; }
  BigInt &operator%=(const BigInt &rhs) { return *this = divide(rhs).second; }
  bool operator==(const BigInt &rhs) const {
    if (sign != rhs.sign || dat.size() != rhs.dat.size()) return false;
    int sz = dat.size();
    REP(i, sz) if (dat[i] != rhs.dat[i]) return false;
    return true;
  }
  bool operator!=(const BigInt &rhs) const { return !(*this == rhs); }
  bool operator<(const BigInt &rhs) const {
    if (sign != rhs.sign) return sign < rhs.sign;
    if (dat.size() != rhs.dat.size()) return sign * dat.size() < rhs.sign * rhs.dat.size();
    for (int i = static_cast<int>(dat.size()) - 1; i >= 0; --i) {
      if (dat[i] != rhs.dat[i]) return dat[i] * sign < rhs.dat[i] * rhs.sign;
    }
    return false;
  }
  bool operator<=(const BigInt &rhs) const { return !(rhs < *this); }
  bool operator>(const BigInt &rhs) const { return rhs < *this; }
  bool operator>=(const BigInt &rhs) const { return !(*this < rhs); }
  BigInt &operator++() { return *this += 1; }
  BigInt operator++(int) { BigInt res = *this; ++*this; return res; }
  BigInt &operator--() { return *this -= 1; }
  BigInt operator--(int) { BigInt res = *this; --*this; return res; }
  BigInt operator+() const { return *this; }
  BigInt operator-() const { BigInt res = *this; res.sign *= -1; return res; }
  BigInt operator+(const BigInt &rhs) const { return BigInt(*this) += rhs; }
  BigInt operator-(const BigInt &rhs) const { return BigInt(*this) -= rhs; }
  BigInt operator*(const BigInt &rhs) const { return BigInt(*this) *= rhs; }
  BigInt operator/(int rhs) const { return BigInt(*this) /= rhs; }
  BigInt operator/(const BigInt &rhs) const { return BigInt(*this) /= rhs; }
  BigInt operator%(int rhs) const { return BigInt(*this) %= rhs; }
  BigInt operator%(const BigInt &rhs) const { return BigInt(*this) %= rhs; }
  friend ostream &operator<<(ostream &os, const BigInt &rhs) {
    if (rhs.sign == -1) os << '-';
    os << (rhs.dat.empty() ? 0 : rhs.dat.back());
    for (int i = static_cast<int>(rhs.dat.size()) - 2; i >= 0; --i) os << setw(lg10_base) << setfill('0') << rhs.dat[i];
    return os;
  }
  friend istream &operator>>(istream &is, BigInt &rhs) { string s; is >> s; rhs = s; return is; }
private:
  vector<long long> karatsuba(vector<long long> &lhs, int lhs_l, int lhs_r, vector<long long> &rhs, int rhs_l, int rhs_r) {
    int lhs_len = lhs_r - lhs_l, rhs_len = rhs_r - rhs_l;
    if (lhs_len < rhs_len) return karatsuba(rhs, rhs_l, rhs_r, lhs, lhs_l, lhs_r);
    vector<long long> res(lhs_len + rhs_len, 0);
    if (rhs_len <= 32) {
      FOR(i, lhs_l, lhs_r) FOR(j, rhs_l, rhs_r) res[(i - lhs_l) + (j - rhs_l)] += lhs[i] * rhs[j];
    } else {
      int mid = (lhs_len + 1) / 2, n = min(lhs_len, mid);
      for (int i = lhs_l; i + mid < lhs_r; ++i) lhs[i] += lhs[i + mid];
      for (int i = rhs_l; i + mid < rhs_r; ++i) rhs[i] += rhs[i + mid];
      vector<long long> tmp = karatsuba(lhs, lhs_l, lhs_l + mid, rhs, rhs_l, rhs_l + n);
      REP(i, tmp.size()) res[mid + i] = tmp[i];
      for (int i = lhs_l; i + mid < lhs_r; ++i) lhs[i] -= lhs[i + mid];
      for (int i = rhs_l; i + mid < rhs_r; ++i) rhs[i] -= rhs[i + mid];
      tmp = karatsuba(lhs, lhs_l, lhs_l + mid, rhs, rhs_l, rhs_l + n);
      REP(i, tmp.size()) { res[i] += tmp[i]; res[mid + i] -= tmp[i]; }
      tmp = karatsuba(lhs, lhs_l + mid, lhs_r, rhs, rhs_l + n, rhs_r);
      REP(i, tmp.size()) { res[mid + i] -= tmp[i]; res[(mid << 1) + i] += tmp[i]; }
    }
    while (!res.empty() && res.back() == 0) res.pop_back();
    return res;
  }
  pair<BigInt, int> divide(int rhs) {
    // assert(!rhs.dat.empty());
    BigInt dividend = *this;
    if (rhs < 0) { dividend.sign *= -1; rhs *= -1; }
    long long rem = 0;
    for (int i = static_cast<int>(dividend.dat.size()) - 1; i >= 0; --i) {
      long long tmp = rem * base + dividend.dat[i];
      dividend.dat[i] = static_cast<int>(tmp / rhs);
      rem = tmp % rhs;
    }
    dividend.trim();
    return {dividend, static_cast<int>(rem)};
  }
  pair<BigInt, BigInt> divide(const BigInt &rhs) {
    // assert(!rhs.dat.empty());
    int k = base / (rhs.dat.back() + 1);
    BigInt dividend = *this, divisor = rhs;
    dividend.sign = 1; divisor.sign = 1;
    dividend *= k; divisor *= k;
    BigInt quo, rem = 0;
    quo.dat.resize(dividend.dat.size());
    int sz = divisor.dat.size();
    for (int i = static_cast<int>(dividend.dat.size()) - 1; i >= 0; --i) {
      rem.dat.insert(rem.dat.begin(), dividend.dat[i]);
      quo.dat[i] = static_cast<int>(((sz < rem.dat.size() ? 1LL * rem.dat[sz] * base : 0) + (sz - 1 < rem.dat.size() ? rem.dat[sz - 1] : 0)) / divisor.dat.back());
      rem -= divisor * quo.dat[i];
      while (rem.sign == -1) { rem += divisor; --quo.dat[i];  }
    }
    quo.sign = sign * rhs.sign; rem.sign = sign;
    quo.trim(); rem.trim();
    return {quo, rem / k};
  }
};
BigInt __gcd(BigInt a, BigInt b) { while (!b.dat.empty()) swap(a %= b, b); return a; }
BigInt __lcm(const BigInt &a, const BigInt &b) { return a / __gcd(a, b) * b; }
BigInt abs(const BigInt &x) { BigInt res = x; res.sign = 1; return res; }
BigInt max(const BigInt &a, const BigInt &b) { return a < b ? b : a; }
BigInt min(const BigInt &a, const BigInt &b) { return a < b ? a : b; }

int main() {
  int n, k1, k2; cin >> n >> k1 >> k2; --k1; --k2;
  vector<int> idx(n), rev(n);
  int now = 0;
  idx[k1] = now;
  rev[now] = k1;
  ++now;
  for (int dist = 1; dist < n; ++dist) {
    if (k1 < k2) {
      if (k1 + dist < n) {
        idx[k1 + dist] = now;
        rev[now] = k1 + dist;
        ++now;
      }
      if (k1 - dist >= 0) {
        idx[k1 - dist] = now;
        rev[now] = k1 - dist;
        ++now;
      }
    } else {
      if (k1 - dist >= 0) {
        idx[k1 - dist] = now;
        rev[now] = k1 - dist;
        ++now;
      }
      if (k1 + dist < n) {
        idx[k1 + dist] = now;
        rev[now] = k1 + dist;
        ++now;
      }
    }
  }
  // REP(i, n) cout << rev[i] << ' ';
  // cout << '\n';
  set<int> broad, emp;
  REP(i, n) broad.emplace(i);
  int q; cin >> q;
  using P = pair<BigInt, int>;
  priority_queue<P, vector<P>, greater<P> > que;
  while (q--) {
    BigInt a, b; cin >> a >> b;
    while (!que.empty() && (que.top().first <= a || (broad.empty() && emp.empty()))) {
      int seat = rev[que.top().second];
      a = max(a, que.top().first);
      que.pop();
      bool br = true;
      if (seat - 1 >= 0) {
        int seat_l = seat - 1;
        if (emp.count(idx[seat_l]) == 1) {
          if (seat_l - 1 < 0 || (broad.count(idx[seat_l - 1]) == 1 || emp.count(idx[seat_l - 1]) == 1)) {
            emp.erase(idx[seat_l]);
            broad.emplace(idx[seat_l]);
          }
        } else {
          br = false;
        }
      }
      if (seat + 1 < n) {
        int seat_r = seat + 1;
        if (emp.count(idx[seat_r]) == 1) {
          if (seat_r + 1 >= n || (broad.count(idx[seat_r + 1]) == 1 || emp.count(idx[seat_r + 1]) == 1)) {
            emp.erase(idx[seat_r]);
            broad.emplace(idx[seat_r]);
          }
        } else {
          br = false;
        }
      }
      (br ? broad : emp).emplace(idx[seat]);
    }
    int seat;
    if (!broad.empty()) {
      seat = *broad.begin();
      broad.erase(seat);
    } else {
      seat = *emp.begin();
      emp.erase(seat);
    }
    cout << rev[seat] + 1 << '\n';
    que.emplace(a + b, seat);
    if (rev[seat] - 1 >= 0) {
      int seat_l = idx[rev[seat] - 1];
      if (broad.count(seat_l) == 1) {
        broad.erase(seat_l);
        emp.emplace(seat_l);
      }
    }
    if (rev[seat] + 1 < n) {
      int seat_r = idx[rev[seat] + 1];
      if (broad.count(seat_r) == 1) {
        broad.erase(seat_r);
        emp.emplace(seat_r);
      }
    }
    // cout << "broad: ";
    // for (int e : broad) cout << e << ' ';
    // cout << '\n';
    // cout << "emp: ";
    // for (int e : emp) cout << e << ' ';
    // cout << '\n';
  }
  return 0;
}
yukicoder

結果

テストケース

ソースコード
