結果
問題 | No.849 yuki国の分割統治 |
ユーザー |
|
提出日時 | 2024-06-21 12:12:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 126 ms / 2,000 ms |
コード長 | 3,139 bytes |
コンパイル時間 | 2,132 ms |
コンパイル使用メモリ | 151,548 KB |
実行使用メモリ | 8,704 KB |
最終ジャッジ日時 | 2024-06-21 12:12:27 |
合計ジャッジ時間 | 6,206 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <algorithm>#include <cassert>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <iostream>#include <numeric>#include <vector>#include <map>#include <set>#include <queue>#include <functional>#include <iomanip>using namespace std;using ll = long long;class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;public:range(int n_):i({0}),n({n_}){}range(int i_,int n_):i({i_}),n({n_}){}I& begin(){return i;}I& end(){return n;}};template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }template<typename T> ostream& operator<<(ostream& os, const vector<T>& obj) { os << "{"; for (const auto& e : obj) os << e << ", "; return os << "}";}template<typename T> ostream& operator<<(ostream& os, const set<T>& obj) { os << "set{"; for (const auto& e : obj) os << e << ", "; return os << "}";}template<typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& obj) { os << "map{"; for (const auto& e : obj) os << e << ", ";return os << "}"; }#ifdef ONLINE_JUDGE#define dump(expr) ;#else#define dump(expr) { cerr << "\033[33m#L" << __LINE__ << ": " << expr << "\033[39m" << endl; }#endifll extgcd(ll a, ll b, ll &x, ll &y) {ll g = a;x = 1;y = 0;if (b != 0)g = extgcd(b, a % b, y, x), y -= (a / b) * x;return g;}namespace solver {ll a, b, c, d;ll n;vector<ll> xs, ys;void read() {cin >> a >> b >> c >> d;cin >> n;xs.resize(n);ys.resize(n);for (int i : range(n)) cin >> xs[i] >> ys[i];}void experiment() {set<pair<ll, ll>> st;dump(a)dump(b)dump(c)dump(d)for (ll s : range(-100, 100))for (ll t : range(-100, 100)) {ll x = a * s + c * t;ll y = b * s + d * t;if (x >= 0 && y >= 0 && x <= 15 && y <= 15) st.insert({x, y});}cout << st << endl;}using RetType = ll;RetType run() {ll A = abs(a * d - b * c);ll gx = gcd(a, c);ll gy = gcd(b, d);set<pair<int, int>> st;dump("A " << A);if (A == 0) {dump(a << " " << b)if (gx == 0) {for (int i : range(n)) st.insert({xs[i], ys[i] % gy});} else {for (int i : range(n)) {ll x = xs[i], y = ys[i];ll m = x / gx;x -= m * gx;y -= m * gy;st.insert({x, y});}}return st.size();}ll h = gy;ll w = A / gy;ll s0, t0;extgcd(b, d, s0, t0);ll u = a * s0 + c * t0;for (int i : range(n)) {ll x = xs[i], y = ys[i];ll m = y / gy;x -= m * u;y -= m * h;x = ((x % w) + w) % w;st.insert({x, y});}return st.size();}} // namespacetemplate <typename F>void run(F f) { if constexpr (std::is_same_v<decltype(f()), void>) f(); else cout << f() << endl; }int main(int argc, char** argv) {cerr << fixed << setprecision(12);cout << fixed << setprecision(12);int testcase = 1;if (argc > 1) testcase = atoi(argv[1]);while (testcase--) {solver::read();}// solver::experiment();run(solver::run);}