QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#278988 | #4378. Ball | chunzhifeng | AC ✓ | 3048ms | 32452kb | C++14 | 1.0kb | 2023-12-08 00:32:54 | 2023-12-08 00:32:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define endl "\n"
#define PII pair<int,int>
const ll INF=0x3f3f3f3f;//3f3f3f3f;
const int mod=998244353;
const int N=4e6+5;
int pr[N],cnt;
bool st[N];
void init(){
st[1]=1;
for(int i=2;i<N;i++){
if(!st[i]) pr[++cnt]=i;
for(int j=1;pr[j]*i<N;j++){
st[pr[j]*i]=1;
if(i%pr[j]==0) break;
}
}
}
bitset<2005>p[2005];
array<int,3>e[N];
int x[2005],y[2005];
void solve(){
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++) p[i].reset();
for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
auto get=[&](int i,int j){
return abs(x[i]-x[j])+abs(y[i]-y[j]);
};
int tot=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++) e[++tot]={get(i,j),i,j};
}
sort(e+1,e+1+tot);
ll ans=0;
for(int i=1;i<=tot;i++){
auto &[v,a,b]=e[i];
if(!st[v]) ans+=(p[a]^p[b]).count();
p[a][b]=p[b][a]=1;
} cout<<ans<<endl;
}
int main(){
init();
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T=1; cin>>T;
while(T--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3048ms
memory: 32452kb
input:
10 2000 80 9 25 39 66 5 63 59 17 45 19 41 21 21 75 21 61 1 65 29 61 11 23 38 51 1 3 41 59 41 61 61 33 45 65 80 49 38 49 45 79 66 60 61 41 56 33 65 57 26 17 36 1 77 11 13 28 25 41 33 23 66 16 4 73 1 1 57 61 32 11 31 29 42 21 37 69 53 59 1 66 54 70 21 57 65 49 49 18 6 5 11 1 1 67 78 49 43 30 27 1 57 7...
output:
306097111 113711265 112644014 306052056 111920257 112598067 290930159 115277403 112743440 307026778
result:
ok 10 lines