結果
問題 | No.1999 Lattice Teleportation |
ユーザー |
|
提出日時 | 2022-03-22 18:25:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 3,212 bytes |
コンパイル時間 | 1,619 ms |
コンパイル使用メモリ | 117,648 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-15 02:12:13 |
合計ジャッジ時間 | 3,327 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#pragma GCC optimize("Ofast")#pragma GCC target("avx2,bmi2,popcnt,lzcnt")#include <cassert>#include <cstdio>#include <cinttypes>#include <unistd.h>#include <sys/stat.h>#include <sys/mman.h>class strictInput{char *p;off_t cur = 0;off_t len = 0;public:explicit strictInput(int fd = 0){struct stat st;fstat(fd, &st);p = (char *)mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);len = st.st_size;}char readChar(){assert(cur != len);return p[cur++];}void unreadChar(){assert(cur != 0);--cur;}bool isEOF() { return cur == len; }void readEOF() { assert(isEOF()); }void readSpace() { assert(readChar() == ' '); }void readEoln() { assert(readChar() == '\n'); }// reads uint64_t in range [from, to]uint64_t readU64(uint64_t from = 0, uint64_t to = UINT64_MAX){uint64_t cur = 0;off_t read_cnt = 0;bool leading_zero = false;while (!isEOF()){char p = readChar();if (!('0' <= p && p <= '9')){unreadChar();break;}uint64_t v = p - '0';assert(cur <= UINT64_MAX / 10);cur *= 10;assert(cur <= UINT64_MAX - v);cur += v;if (read_cnt == 0 && v == 0)leading_zero = true;++read_cnt;}if (cur == 0)assert(read_cnt == 1);elseassert(!leading_zero);assert(from <= cur && cur <= to);return cur;}// reads int64_t in range [from, to]int64_t readI64(int64_t from = INT64_MIN, int64_t to = INT64_MAX){uint64_t cur = 0;off_t read_cnt = 0;bool leading_zero = false;bool leading_minus = readChar() == '-';if (!leading_minus)unreadChar();while (!isEOF()){char p = readChar();if (!('0' <= p && p <= '9')){unreadChar();break;}uint64_t v = p - '0';assert(cur <= UINT64_MAX / 10);cur *= 10;assert(cur <= UINT64_MAX - v);cur += v;if (read_cnt == 0 && v == 0)leading_zero = true;++read_cnt;}if (cur == 0)assert(read_cnt == 1 && !leading_minus);elseassert(!leading_zero);if (cur <= INT64_MAX){int64_t ret = cur;if (leading_minus)ret = -ret;assert(from <= ret && ret <= to);return ret;}else{assert(leading_minus && cur == uint64_t(INT64_MIN));assert(from == INT64_MIN);return INT64_MIN;}}};#include <algorithm>#include <iostream>#include <numeric>#include <tuple>#include <vector>using namespace std;int main(){strictInput Inp;int N;N = Inp.readI64(1, 100'000);Inp.readEoln();vector<pair<int, int>> V;for (int i = 0; i < N; ++i){int a, b;a = Inp.readI64(-1'000'000'000, 1'000'000'000);Inp.readSpace();b = Inp.readI64(-1'000'000'000, 1'000'000'000);Inp.readEoln();if (a == 0 && b == 0)continue;if (a < 0)a = -a, b = -b;V.emplace_back(a, b);}Inp.readEOF();sort(V.begin(), V.end(), [&](auto a, auto b){ return (long long)a.first * b.second > (long long)b.first * a.second; });long long x = 0, y = 0;__int128 ans = 1;for (auto [dx, dy] : V){ans += (__int128)x * dy - (__int128)y * dx;ans += gcd(dx, dy);x += dx;y += dy;}const int MOD = 1'000'000'007;int ret = ans % MOD;if (ret < 0)ret += MOD;cout << ret << endl;}