結果

問題 No.1550 nullくんの町清掃 / null's Town Cleaning
ユーザー オオスミ
提出日時 2021-09-10 12:28:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 11 ms / 2,000 ms
コード長 14,062 bytes
コンパイル時間 2,441 ms
コンパイル使用メモリ 215,900 KB
最終ジャッジ日時 2025-01-24 09:09:08
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#include <set>
#include <map>
#include <stack>
#include <iomanip>
#include <tuple>
#include <cstdio>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#include <cstdint>
#include <cfenv>
#include <list>
#include<string.h>
#include <iterator>
#include <bits/stdc++.h>
#define ll long long
#define rep(i, s, n) for (ll i = (ll)(s); i < (ll)(n); i++)
#define rrep(i, s, n) for (ll i = (ll)(s); i > (ll)(n); i--)
#define all(a) (a).begin(), a.end()
#define rall(a) (a).rbegin(),(a).rend()
#define PI 3.14159265359
#define mod 1000000007
#define P pair<ll, ll>
#define V vector<ll>
#define C vector<char>
#define B vector<bool>
#define endl '\n'
const ll MAX = 510000;
const ll MOD =1000000007;
using namespace std;
using graph = vector<vector<ll>>;
struct edge{
//
//
//operator
ll from, to;
ll cost;
ll capa;
edge(ll s, ll d) : from(s), to(d) { cost = 0; capa = 0; }
edge(ll s, ll d, ll w) : from(s), to(d), cost(w) { capa = 0; }
edge(ll s, ll d, ll x, ll y) :from(s), to(d), cost(x), capa(y) {}
bool operator < (const edge& x) const {
return cost < x.cost;
}
};
using Graph=vector<vector<edge>>;//
//
vector<ll> Dijkstra(ll i, vector<vector<edge>> Graph) {
//i:
//Graph:
ll n =Graph.size();
vector<ll> d(n, LONG_MAX);
d[i] = 0;
priority_queue<
pair<ll, ll>,//pair
vector<pair<ll, ll>>,//
greater<pair<ll, ll>>//
> q;
q.push({0, i});//: :
while (!q.empty()) {
pair<ll, ll> p = q.top();
q.pop();
int v = p.second;
if (d[v] < p.first) {
continue;
}
for (auto x : Graph[v]) {
if (d[x.to] > d[v] + x.cost) {
d[x.to] = d[v] + x.cost;
q.push({d[x.to], x.to});
}
}
}
return d;
}
ll fac[MAX], finv[MAX], inv[MAX];
//
void cominit()
{
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (ll i = 2; i < MAX; i++)
{
fac[i] = fac[i - 1] * i% MOD;
inv[i] = MOD - inv[MOD % i] * (MOD / i)% MOD;
finv[i] = finv[i - 1] * inv[i]% MOD;
}
}
// mod. m a a^{-1}
ll modinv(ll a, ll m)
{
ll b = m, u = 1, v = 0;
while (b)
{
ll t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
u %= m;
if (u < 0)
u += m;
return u;
}
// nCk,n<=10^7,k<=10^7
ll com(ll n, ll k)
{
if (n < k)
return 0;
if (n < 0 || k < 0)
return 0;
return fac[n] * (finv[k] * finv[n - k]% MOD) % MOD;
}
//nCk,n<=10^9,k<=10^7
ll com2(ll n,ll k){
ll res,bs=1,bb=1;
for(ll i=0;i<k;i++){
bs=(bs*(n-i))%mod;
bb=(bb*(i+1))%mod;
}
res=modinv(bb,mod)%mod;
res=(res*bs)%mod;
return res;
}
// nPk
ll per(ll n, ll k)
{
if (n < k)
return 0;
if (n < 0 || k < 0)
return 0;
return fac[n] * (finv[n - k] % MOD) % MOD;
}
/* */
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
/**/
ll lcm(ll a, ll b)
{
return a / gcd(a, b) * b;
}
/**/
double dist(pair<double, double> a, pair<double, double> b)
{
return sqrt(pow((a.first - b.first), 2) + pow((a.second - b.second), 2));
}
//
double ism(double aa, ll p)
{
double ap = aa;
double ans = 1;
while (p > 0)
{
//cout<<"p="<<p<<",ap="<<ap<<endl;
if (p & 1)
{ //
ans *= ap;
}
p /= 2;
ap = ap * ap;
}
return ans;
}
//()
ll ismm(ll aa, ll p,ll m)
{
ll ap = aa;
ll ans = 1;
while (p > 0)
{
//cout<<"p="<<p<<",ap="<<ap<<endl;
if (p & 1)
{ //
ans = (ans * ap) % m;
}
p /= 2;
ap = (ap * ap) % m;
}
return ans;
}
ll oddXOR(ll a) { return (a+1)/2 % 2; }
ll XOR(ll a) {
if (a % 2 == 1) return oddXOR(a);
else return oddXOR(a+1) ^ (a+1);
}
double median(V a){//
sort(all(a));
if(a.size()%2==1){
return a[(a.size()-1)/2];
}
else{
return (a[(a.size()-1)/2]+a[(a.size()-1)/2+1])/2.0;
}
}
struct UnionFind
{
vector<ll> par;
ll forest;
UnionFind(ll n) : par(n, -1) {forest=n;}
ll root(ll x)
{
if (par[x] < 0)
return x;
else
return par[x] = root(par[x]);
}
bool issame(ll x, ll y)
{
return root(x) == root(y);
}
bool merge(ll x, ll y)
{
x = root(x);
y = root(y);
if (x == y){
return false;
}
if (par[x] > par[y]){
swap(x, y); // merge technique
}
forest--;
par[x] += par[y];
par[y] = x;
return true;
}
ll size(ll x)
{
return -par[root(x)];
}
};
//
vector<pair<long long, long long> > prime_factorize(long long N) {
vector<pair<long long, long long> > res;
for (long long a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
long long ex = 0; //
//
while (N % a == 0) {
++ex;
N /= a;
}
// push
res.push_back({a, ex});
}
//
if (N != 1) res.push_back({N, 1});
return res;
}
//
vector<long long> enum_divisors(long long N) {
vector<long long> res;
for (long long i = 1; i * i <= N; ++i) {
if (N % i == 0) {
res.push_back(i);
// i N/i push
if (N/i != i){
res.push_back(N/i);
}
}
}
//
sort(res.begin(), res.end());
return res;
}
//
ll Keta(ll x){
ll cnt=1;
while(x>=10){
x/=10;
cnt++;
}
return cnt;
}
bool is_prime(long long N) {
if (N == 1) return false;
for (long long i = 2; i * i <= N; ++i) {
if (N % i == 0) return false;
}
return true;
}
//
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
__int128 parse(string &s) {
__int128 ret = 0;
for (int i = 0; i < s.length(); i++)
if ('0' <= s[i] && s[i] <= '9')
ret = 10 * ret + s[i] - '0';
return ret;
}
//109+7mod
template <std::uint_fast64_t Modulus> class modint {
using u64 = std::uint_fast64_t;
public:
u64 a;
constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
constexpr u64 &value() noexcept { return a; }
constexpr const u64 &value() const noexcept { return a; }
constexpr modint operator+(const modint rhs) const noexcept {
return modint(*this) += rhs;
}
constexpr modint operator-(const modint rhs) const noexcept {
return modint(*this) -= rhs;
}
constexpr modint operator*(const modint rhs) const noexcept {
return modint(*this) *= rhs;
}
constexpr modint operator/(const modint rhs) const noexcept {
return modint(*this) /= rhs;
}
constexpr modint &operator+=(const modint rhs) noexcept {
a += rhs.a;
if (a >= Modulus) {
a -= Modulus;
}
return *this;
}
constexpr modint &operator-=(const modint rhs) noexcept {
if (a < rhs.a) {
a += Modulus;
}
a -= rhs.a;
return *this;
}
constexpr modint &operator*=(const modint rhs) noexcept {
a = a * rhs.a % Modulus;
return *this;
}
constexpr modint &operator/=(modint rhs) noexcept {
u64 exp = Modulus - 2;
while (exp) {
if (exp % 2) {
*this *= rhs;
}
rhs *= rhs;
exp /= 2;
}
return *this;
}
};
//12
struct all_init
{
all_init()
{
cout << fixed << setprecision(9);
}
} All_init;
//Bit
// 1-indexed
struct BIT {
private:
vector<int> bit;
int N;
public:
BIT(int size) {
N = size;
bit.resize(N + 1);
}
//
void add(int a, int w) {
for (int x = a; x <= N; x += x & -x) bit[x] += w;
}
// 1~N
int sum(int a) {
int ret = 0;
for (int x = a; x > 0; x -= x & -x) ret += bit[x];
return ret;
}
};
/* SegTree<X>(n,fx): (X, fx)n
set(int i, X x), build(): ixO(n)
update(i,x): i x O(log(n))
query(a,b): [a,b) fxO(log(n))
*/
template <typename X>
struct SegTree {
using FX = function<X(X, X)>;
int n;
FX fx;
vector<X> dat;
SegTree(int n_, FX fx_): n(), fx(fx_),dat(n_ * 4) {
int x = 1;
while (n_ > x) {
x *= 2;
}
n = x;
}
void set(int i, X x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
}
void update(int i, X x) {
i += n - 1;
dat[i] = x;
while (i > 0) {
i = (i - 1) / 2; // parent
dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
}
}
// the minimum element of [a,b)
X query(int a, int b) { return query_sub(a, b, 0, 0, n); }
X query_sub(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) {
return pow(2,31);
} else if (a <= l && r <= b) {
return dat[k];
} else {
X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return fx(vl, vr);
}
}
/* debug */
inline X operator[](int a) { return query(a, a + 1); }
void print() {
for (int i = 0; i < n; ++i) {
cout << (*this)[i];
if (i != n) cout << ",";
}
cout << endl;
}
};
struct Zip{
map<ll,ll>mp;
Zip(vector<ll>a){
rep(i,0,a.size()){
mp[a[i]]=0;
}
ll size=0;
for(auto &x:mp){//&
x.second=size;
size++;
}
}
ll zip(ll n){
return mp[n];
}
ll size(){
return mp.size();
}
};
// 24 Clock
struct Clock{
int hour; // (0~23)
int minute; // (0~59)
int second; // (0~59)
// set
// : set
// : int h, int m, int s ()
// :
// :
// 3
// hour, minute, second
void set(int h,int m,int s){
hour=h;
minute=m;
second=s;
}
// to_str
// : to_str
// :
// : string
// :
//
//
// "HH:MM:SS"
// HHMMSS2
string to_str(){
string res;
if(hour<10){
res+="0";
}
res+=to_string(hour);
res+=":";
if(minute<10){
res+="0";
}
res+=to_string(minute);
res+=":";
if(second<10){
res+="0";
}
res+=to_string(second);
return res;
}
// shift
// : shift
// : int diff_second
// :
// :
// diff_second ()
// diff_second
// diff_second
// diff_second -86400 ~ 86400
void shift(int diff_second){
int diff_hour=diff_second/3600;
diff_second%=3600;
int diff_minute=diff_second/60;
diff_second%=60;
second+=diff_second;
if(second>=60){
second-=60;
minute+=1;
}
else if(second<0){
second+=60;
minute-=1;
}
minute+=diff_minute;
if(minute>=60){
minute-=60;
hour+=1;
}
else if(minute<0){
minute+=60;
hour-=1;
}
hour+=diff_hour;
if(hour>=24){
hour-=24;
}
else if(hour<0){
hour+=24;
}
}
};
int main() {
ll n;
cin>>n;
cout<<n%mod<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0