QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#391969#8177. Sum is Integeri_am_noob#WA 0ms3752kbC++141.5kb2024-04-16 22:59:272024-04-16 22:59:28

Judging History

This is the latest submission verdict.

  • [2024-04-16 22:59:28]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3752kb
  • [2024-04-16 22:59:27]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using pii=pair<int,int>;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())

const int mod=998244353,N=200005;

const ll p=1945555039024054273,q=9223372036737335297;

ll mul(ll x, ll y, ll mod){return __int128(x)*y%mod;}
ll Pow(ll x, ll y, ll mod){ll res=1; for(; y; y>>=1,x=mul(x,x,mod)) if(y&1) res=mul(res,x,mod); return res;}

void ahcorz(){
    int n; cin >> n;
    vector<pair<ll,ll>> vec(n+1);
    vec[0]={0,0};
    vector<ll> vec2(n+1);
    vec2[0]=0;
    for(int i=0; i<n; ++i){
        int x,y; cin >> x >> y;
        x%=y;
        vec[i+1]={(__int128(0)+vec[i].first+mul(x,Pow(y,p-2,p),p))%p,(__int128(0)+vec[i].second+mul(x,Pow(y,q-2,q),q))%q};
        vec2[i+1]=vec[i+1].first-vec[i+1].second;
        cout << vec[i+1].first << ' ' << vec[i+1].second << "\n";
    }
    sort(all(vec2));
    ll res=0;
    for(int i=0; i<sz(vec2); ++i){
        res+=upper_bound(all(vec2),vec2[i])-lower_bound(all(vec2),vec2[i]);
    }
    res-=sz(vec2);
    res/=2;
    for(int i=0; i<sz(vec2); ++i){
        res+=upper_bound(all(vec2),vec2[i]-p)-lower_bound(all(vec2),vec2[i]-p);
        res+=upper_bound(all(vec2),vec2[i]+q)-lower_bound(all(vec2),vec2[i]+q);
        res+=upper_bound(all(vec2),vec2[i]-p+q)-lower_bound(all(vec2),vec2[i]-p+q);
    }
    cout << res << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int t=1;// cin >> t;
    while(t--){
        ahcorz();
    }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3752kb

input:

4
1 6
1 3
1 2
1 2

output:

1621295865853378561 1537228672789555883
972777519512027137 4611686018368667649
1 1
972777519512027138 4611686018368667650
2

result:

wrong answer 1st words differ - expected: '2', found: '1621295865853378561'