Submission #890980

#TimeUsernameProblemLanguageResultExecution timeMemory
890980Muhammad_AneeqPairs (IOI07_pairs)C++17
37 / 100
4074 ms29012 KiB
/* بسم الله الرحمن الرحيم Author: (:Muhammad Aneeq:) */ #include <iostream> #include <map> #include <set> #include <vector> #include <algorithm> using namespace std; #define int long long inline int dis(vector<int>&a,vector<int>&b) { int z=0; for (int j=0;j<b.size();j++) z+=abs(a[j]-b[j]); return z; } inline void solve() { long long B,N,D,M; cin>>B>>N>>D>>M; int a[N][B]; vector<int>mi(B,1e9+10),ma(B,0); map<vector<int>,int>d; for (int i=0;i<N;i++) { for (int j=0;j<B;j++) cin>>a[i][j]; for (int j=0;j<B;j++) { mi[j]=min(mi[j],a[i][j]); ma[j]=max(ma[j],a[i][j]); } } if (dis(mi,ma)<=D) { cout<<(N*(N-1))/2<<endl; return; } if (B==1) { vector<int>z; for (int i=0;i<N;i++) z.push_back(a[i][0]); sort(begin(z),end(z)); int ans=0; for (int i=0;i<N;i++) { int x=upper_bound(begin(z),end(z),z[i]+D)-begin(z); ans+=x-i-1; } cout<<ans<<endl;return; } int g=1; for (int i=0;i<B;i++) g*=D; int ans=0; set<vector<int>>s; for (int i=0;i<N;i++) { vector<int>g; for (int j=0;j<B;j++) g.push_back(a[i][j]); d[g]++; s.insert(g); } vector<vector<int>>z={begin(s),end(s)}; int y=z.size(); // cout<<y<<endl; if (B==3) { M=min(M,D); for (int i=0;i<y;i++) { for (int j=max(mi[0],z[i][0]-M);j<=min(ma[0],z[i][0]+M);j++) { for (int k=max(mi[1],z[i][1]-(M-abs(z[i][0]-j)));k<=min(ma[1],z[i][1]+(M-abs(z[i][0]-j)));k++) { for (int l=max(mi[2],z[i][2]-(M-abs(z[i][0]-j)+abs(z[i][1]-k)));l<=min(ma[2],z[i][2])+(M-abs(z[i][0]-j)+abs(z[i][1]-k));l++) { if (d.find({j,k,l})==d.end()) continue; vector<int>y={j,k,l}; int di=dis(z[i],y); if (di<=D) { if (y==z[i]) ans+=d[z[i]]*(d[z[i]]-1); else ans+=d[z[i]]*d[y]; } } } } } cout<<ans/2<<endl; return; } for (int i=0;i<z.size();i++) { int g=d[z[i]]; ans+=(g*(g-1))/2; for (int j=i+1;j<z.size();j++) { int di=dis(z[i],z[j]); if (di<=D) ans+=d[z[i]]*d[z[j]]; } } cout<<ans<<endl; } signed main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); solve(); }

Compilation message (stderr)

pairs.cpp: In function 'long long int dis(std::vector<long long int>&, std::vector<long long int>&)':
pairs.cpp:16:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (int j=0;j<b.size();j++)
      |                ~^~~~~~~~~
pairs.cpp: In function 'void solve()':
pairs.cpp:101:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for (int i=0;i<z.size();i++)
      |                ~^~~~~~~~~
pairs.cpp:105:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for (int j=i+1;j<z.size();j++)
      |                    ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...