Submission #912864

#TimeUsernameProblemLanguageResultExecution timeMemory
912864Faisal_SaqibIdeal city (IOI12_city)C++17
55 / 100
86 ms2908 KiB
#pragma once #include <vector> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <assert.h> #include <iostream> #include <cmath> #include <queue> #define ll long long using namespace std; /* 1 11 N <= 2e2 O(n^2) 2 21 N <= 2e3 O(n^2) 3 23 N <= 1e5 4 45 N <= 1e5 For 3 any two cell such x[i]<=x[j] then for all x such that x[i]<=x<=x[j] there is non empty cell there */ const int N=2001; vector<int> ma[N]; bool vis[N]; int h[N]; int DistanceSum(int N, int X[], int Y[]) { ll n=N; ll x[n],y[n]; for(int i=0;i<n;i++) { x[i]=X[i]; y[i]=Y[i]; } if(n<=2000) { for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if((abs(x[i]-x[j])+abs(y[i]-y[j]))==1) { ma[i].push_back(j); ma[j].push_back(i); } } } long long ans1=0; long long mod=1e9; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { h[j]=0; vis[j]=0; } queue<int> q; q.push(i); vis[i]=1; long long ans=0; while(q.size()) { int x=q.front(); ans+=(long long)h[x]; q.pop(); for(int y:ma[x]) { if(!vis[y]) { vis[y]=1; h[y]=h[x]+1; q.push(y); } } } ans1+=ans; } ans1/=2; return ans1%mod; } long long other=0; long long mod=1e9; sort(x,x+n); sort(y,y+n); long long tot=0; for(int i=0;i<n;i++) tot+=x[i]; long long pr=0; for(ll i=0;i<n;i++) { pr+=x[i]; tot-=x[i]; other+=(((i+1)*x[i])-pr); other+=(tot-((n-i-1)*x[i])); } long long sm=(other/2)%mod; tot=0; pr=0; other=0; for(ll j=0;j<n;j++) { tot+=y[j]; } for(ll i=0;i<n;i++) { pr+=y[i]; tot-=y[i]; other+=(((i+1)*y[i])-pr); other+=(tot-((n-i-1)*y[i])); } other/=2; other%=mod; return (other+sm)%mod; }

Compilation message (stderr)

city.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...