結果

問題 No.8073 -
ユーザー MtSakaMtSaka
提出日時 2021-04-01 20:03:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,687 bytes
コンパイル時間 3,123 ms
コンパイル使用メモリ 202,108 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-18 01:12:19
合計ジャッジ時間 3,466 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

//GIVE ME AC!!!!!!!!!!!!!!!!!
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
//#include<atcoder/all>
#define ll long long
#define MOD 1000000007
#define mod 998244353
#define floatset(n) fixed<<setprecision(n)
#define all(n) n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
#define rep(i, s, n) for (ll i=s;i<(ll)(n);i++)
//#define mint modint1000000007
using namespace std;
//using namespace atcoder;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const double PI=acos(-1);
//素数判定 O(√N)
ll prime(ll num){
    if (num < 2){
        return 0;
    }
    else if (num == 2){
        return 1;
    }
    else if (num % 2 == 0){
        return 0;
    }
    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2){
        if (num % i == 0){
            return 0;
        }
    }
    return 1;
}
//素因数分解(約数列挙) O(√N)
vector<ll> divisor(ll n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
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;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
  sort(all(res));
    return res;
}
//最大公約数
ll gcd(ll x,ll y){
    if(x<y) swap(x,y);
    //xの方が常に大きい
    ll r;
    while(y>0){
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}
//最小公倍数
ll lcm(ll x,ll y){
    return (ll)(x/gcd(x,y))*y;
}
//転倒数
ll merge_cnt(vector<ll> &a) {
    ll n = a.size();
    if (n <= 1) { return 0; }
    ll cnt = 0;
    vector<ll> b(a.begin(), a.begin()+n/2);
    vector<ll> c(a.begin()+(n/2), a.end());
    cnt += merge_cnt(b);
    cnt += merge_cnt(c);
    ll ai = 0, bi = 0, ci = 0;
    // merge の処理
    while (ai < n) {
        if ( bi < b.size() && (ci == c.size() || b[bi] <= c[ci]) ) {
            a[ai++] = b[bi++];
        } 
      else {
            cnt += n / 2 - bi;
            a[ai++] = c[ci++];
        }
    }
    return cnt;
}
ll modinv(ll a){
  ll b=MOD,x=1,y=0;
  while(b>0){
    x-=y*(a/b);
    swap(x,y);
    a=a%b;
    swap(a,b);
  }
  x=x%MOD; 
  if(x>=0){
    return x;
  }
  else{
    return x+MOD;
  }
}
 
ll COM(ll n,ll k){
  ll res=1;
  for(ll i=1;i<=k;i++){
    res=res*(n-i+1)%MOD*modinv(i)%MOD;
  }
  return res;
}
 
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }
    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }
    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
const ll inf = 1e18;
typedef pair<long long, long long > P;
struct Edge {
    long long to;
    long long cost;
};
using Graph = vector<vector<Edge>>;
using graph=vector<vector<ll>>;
void dijkstra(const Graph& G, ll s, vector<long long>& dis) {
    ll N = G.size();
    dis.resize(N, inf);
    priority_queue<P, vector<P>, greater<P>> pq;
    pq.emplace(dis[s], s);
    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        ll v = p.second;
        if (dis[v] < p.first) {
            continue;
        }
        if (v == s) {
            for (auto& e : G[v]) {
                if (dis[e.to] > e.cost) {
                    dis[e.to] = e.cost;
                    pq.emplace(dis[e.to], e.to);
                }
            }
        }
        else {
            for (auto& e : G[v]) {
                if (dis[e.to] > dis[v] + e.cost) {
                    dis[e.to] = dis[v] + e.cost;
                    pq.emplace(dis[e.to], e.to);
                }
            }
        }
    }
}
int main(){
}
0