結果
| 問題 |
No.953 席
|
| コンテスト | |
| ユーザー |
 emthrm
|
| 提出日時 | 2019-12-16 10:36:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,733 bytes |
| コンパイル時間 | 3,165 ms |
| コンパイル使用メモリ | 155,904 KB |
| 最終ジャッジ日時 | 2025-01-08 11:46:19 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 16 WA * 9 |
ソースコード
#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;
}