QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#349483 | #8340. 3 Sum | ucup-team1134# | WA | 173ms | 4004kb | C++23 | 3.8kb | 2024-03-10 02:23:05 | 2024-03-10 02:23:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int MAX=300005,INF=1<<30;
const ll mod=300000000000000011LL;
string add(string a,string b){
if(si(a)<si(b)) swap(a,b);
for(int i=0;i<si(b);i++){
a[si(a)-1-i]+=int(b[si(b)-1-i]-'0');
if(a[si(a)-1-i]>'9'&&si(a)-1-i){
a[si(a)-1-i]-=10;
a[si(a)-1-i-1]++;
}
}
for(int i=si(a)-1;i>=1;i--){
if(a[i]>'9'){
a[i]-=10;
a[i-1]++;
}
}
string res;
if(a[0]>'9'){
a[0]-=10;
res+='1';
}
res+=a;
for(int i=si(res)-1;i>=0;i--){
if(res[i]>'9'){
res[i]-=10;
res[i-1]++;
}
}
reverse(all(res));
while(si(res)>1&&res.back()=='0') res.pop_back();
reverse(all(res));
return res;
}
ll N,K;
string calc(string Z){
if(si(Z)<=K) return Z;
string res="0";
while(si(Z)){
string ad;
if(si(Z)<=K){
ad=Z;
Z.clear();
}else{
ad=Z.substr(si(Z)-K,K);
for(int t=0;t<K;t++) Z.pop_back();
}
res=add(res,ad);
}
return calc(res);
}
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int D=1;
vector<ll> P(D),de(D);
cin>>N>>K;
vector<vector<ll>> X(N,vector<ll>(D));
{
string S(K,'9');
for(int j=0;j<D;j++){
ll re=0;
for(int k=0;k<si(S);k++){
re*=10;
re+=(S[k]-'0');
re%=mod;
}
de[j]=re;
}
}
for(int i=0;i<N;i++){
string SS;cin>>SS;
reverse(all(SS));
vector<ll> A(K);
for(int j=0;j<si(SS);j++){
A[j%K]+=(SS[j]-'0');
}
while(1){
bool upd=false;
for(int j=0;j<K;j++){
ll z=A[j]/10;
if(z) upd=true;
A[j]-=z*10;
int to=j+1;
if(to==K) to=0;
A[to]+=z;
}
if(!upd) break;
}
reverse(all(A));
string S;
for(ll x:A) S+=char('0'+x);
while(si(SS)){
string ad;
if(si(SS)<=K){
ad=SS;
SS.clear();
}else{
ad=SS.substr(si(SS)-K,K);
for(int t=0;t<K;t++) SS.pop_back();
}
}
for(int j=0;j<D;j++){
ll re=0;
for(int k=0;k<si(S);k++){
re*=10;
re+=(S[k]-'0');
re%=mod;
}
X[i][j]=re;
}
}
sort(all(X));
ll ans=0;
for(int j=0;j<N;j++){
for(int k=j;k<N;k++){
for(ll z=0;z<3;z++){
vector<ll> Y(D);
for(int x=0;x<D;x++){
Y[x]=de[x]*z+mod+mod-X[j][x]-X[k][x];
Y[x]%=mod;
}
int r=upper_bound(X.begin(),X.begin()+j+1,Y)-X.begin();
int l=lower_bound(X.begin(),X.begin()+j+1,Y)-X.begin();
ans+=r-l;
}
}
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
input:
4 1 0 1 10 17
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 20ms
memory: 3608kb
input:
500 859 7118711592236878297922359501613604144948355616986970837340677671376753603836852811886591300370143151943368529129749813118476151865844255212534355441611481420938483178075143062691345257288242460282715389758789648541099090735875617822348551942134616963557723055980260082230902505269975518146286...
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 173ms
memory: 4004kb
input:
500 17336 11871159223687829792235950161360414494835561698697083734067767137675360383685281188659130037014315194336852912974981311847615186584425521253435544161148142093848317807514306269134525728824246028271538975878964854109909073587561782234855194213461696355772305598026008223090250526997551814628...
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 89ms
memory: 3756kb
input:
500 1 751324443898124078584847834484321089092662321556147445230263526014359393841194947303407593948729802551881289193716611867931891257925091769456350249725997883453296895094445731130479434019358742162771547784250401546380268386074363779242500860317042151185119666027858022664683818314351285215150806...
output:
2277515
result:
wrong answer 1st numbers differ - expected: '2327631', found: '2277515'