oj.uz

Submission #151011

# Submission time Handle Problem Language Result Execution time Memory
151011 2019-09-01T14:48:55 Z JustInCase FunctionCup Museum (FXCUP4_museum) C++17
100 / 100
 561 ms 18400 KB 
#include <bits/stdc++.h>

#ifdef LOCAL
	#include "grader.cpp"
#else
	#include "museum.h"
#endif

#define count_similar_pairs CountSimilarPairs
#define int32_t int
#define int64_t long long

int64_t count_similar_pairs(std::vector< int32_t > a, std::vector< int32_t > b, std::vector< int32_t > c) {
	std::map< int32_t, int32_t > cntA, cntB, cntC;
	std::map< std::pair< int32_t, int32_t >, int32_t > cntAB, cntAC, cntBC;
	std::map< std::tuple< int32_t, int32_t, int32_t >, int32_t > cntABC;

	int32_t n = a.size();
	for(int32_t i = 0; i < n; i++) {
		cntA[a[i]]++;
		cntB[b[i]]++;
		cntC[c[i]]++;

		cntAB[{ a[i], b[i] }]++;
		cntAC[{ a[i], c[i] }]++;
		cntBC[{ b[i], c[i] }]++;
	
		cntABC[{ a[i], b[i], c[i] }]++;
	}

	int64_t ans = 0;
	for(auto &x : cntA) {
		ans += (int64_t) x.second * (x.second - 1) / 2;
	}
	for(auto &x : cntB) {
		ans += (int64_t) x.second * (x.second - 1) / 2;
	}
	for(auto &x : cntC) {
		ans += (int64_t) x.second * (x.second - 1) / 2;
	}

	for(auto &x : cntAB) {
		ans -= (int64_t) x.second * (x.second - 1) / 2;
	}
	for(auto &x : cntAC) {
		ans -= (int64_t) x.second * (x.second - 1) / 2;
	}
	for(auto &x : cntBC) {
		ans -= (int64_t) x.second * (x.second - 1) / 2;
	}

	for(auto &x : cntABC) {
		ans += (int64_t) x.second * (x.second - 1) / 2;
	}

	return ans;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 6 ms 888 KB Output is correct
10 Correct 6 ms 888 KB Output is correct

Subtask #2
73.0 / 73.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 4 ms 632 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 6 ms 888 KB Output is correct
10 Correct 6 ms 888 KB Output is correct
11 Correct 14 ms 1628 KB Output is correct
12 Correct 14 ms 1016 KB Output is correct
13 Correct 122 ms 6564 KB Output is correct
14 Correct 218 ms 9116 KB Output is correct
15 Correct 323 ms 12444 KB Output is correct
16 Correct 68 ms 5172 KB Output is correct
17 Correct 134 ms 5248 KB Output is correct
18 Correct 377 ms 11932 KB Output is correct
19 Correct 561 ms 18300 KB Output is correct
20 Correct 536 ms 18400 KB Output is correct