結果

問題 No.1999 Lattice Teleportation
ユーザー cologne
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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);
else
assert(!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);
else
assert(!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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0