oj.uz

Submission #698531

# Submission time Handle Problem Language Result Execution time Memory
698531 2023-02-13T17:21:44 Z arneves Ideal city (IOI12_city) C++17
23 / 100
 33 ms 3768 KB 
/*
	  ______  _____  _______ _     _ _______ __   _  _____  _  _  _
	 |_____/ |     | |       |____/  |______ | \  | |     | |  |  |
	 |    \_ |_____| |_____  |    \_ ______| |  \_| |_____| |__|__|
	
	
		   .      .           .      .           .      .    	
		   _\/  \/_           _\/  \/_           _\/  \/_    	
			_\/\/_             _\/\/_             _\/\/_     	
		_\_\_\/\/_/_/_     _\_\_\/\/_/_/_     _\_\_\/\/_/_/_ 	
		 / /_/\/\_\ \       / /_/\/\_\ \       / /_/\/\_\ \  	
			_/\/\_             _/\/\_             _/\/\_     	
			/\  /\             /\  /\             /\  /\     	
		   '      '           '      '           '      '    	
	
*/
 
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
 
 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>

using namespace std;

/*
vector<int> dist(int s, vector<vector<int> > &adj){
	int n=adj.size();
	queue<int> q;
	q.push(s);
	vector<int> dist(n, -1);
	dist[s]=0;
	
	while(!q.empty()){
		int v=q.front();
		q.pop();
		
		for(int u: adj[v]){
			if(dist[u]==-1){
				q.push(u);
				dist[u]=dist[v]+1;
			}
		}
	}
	
	return dist;
}*/

int DistanceSum(int N, int *X, int *Y) {
	
	long long ans=0;
	
	map<int,long long> x;
	map<int,long long> y;
	
	for(int i=0; i<N; i++){
		x[X[i]]++;
		y[Y[i]]++;
	}
	
	long long somax=0;
	long long somay=0;
	
	for(auto u: x){
		ans+=(somax*(((long long) N)-somax));
		ans%=1'000'000'000;
		somax+=u.second;
	}
	
	for(auto u: y){
		ans+=(somay*(((long long) N)-somay));
		ans%=1'000'000'000;
		somay+=u.second;
	}
	
	return ans;
	
	/*vector<vector<int> > adj(N, vector<int>());
	
	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){
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	
	for(int i=0; i<N; i++){
		
		vector<int> d=dist(i, adj);
		
		for(int j=i+1; j<N; j++){
			ans+=d[j];
			if(ans>=1000'000'000) ans-=1000'000'000;
		}
	}
	
	
	return ans;*/
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 6 ms 684 KB Output is correct
3 Correct 12 ms 1216 KB Output is correct
4 Correct 12 ms 1108 KB Output is correct
5 Correct 27 ms 1908 KB Output is correct
6 Correct 25 ms 1856 KB Output is correct
7 Correct 28 ms 2192 KB Output is correct
8 Correct 27 ms 1876 KB Output is correct
9 Correct 26 ms 2084 KB Output is correct
10 Correct 33 ms 3768 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -