oj.uz

Submission #148956

# Submission time Handle Problem Language Result Execution time Memory
148956 2019-09-01T05:27:39 Z OnePiece(#3770, lxfind) FunctionCup Museum (FXCUP4_museum) C++17
100 / 100
 472 ms 14444 KB 
#include "museum.h"
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <climits>
#include <cstring>
#include <ctime>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define REP(i,t) for(int i=0; i<(t); i++)
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define FORD(i,a,b) for (int i = (a); i >= (b); i--)
#define FORL(i,s,t) for(L i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)
#define EPS 1e-11
#define EQ(a, b) (fabs((a) - (b)) <= EPS)
#define POS(a) ((a) >= EPS)
#define NEG(a) ((a) <= -EPS)
#define BG(a, b) ((a) - (b) >= EPS)
#define LS(a, b) ((b) - (a) >= EPS)
#define CLR(a, x) memset( a, x, sizeof( a ) )
#define PI (atan(1.0) * 4)
#define SQ(x) ((x) * (x))
#define DIST(x1, y1, x2, y2) (sqrt(SQ((x1) - (x2)) + SQ((y1) - (y2))))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define setmin(a, b) (a = min(a, b))
#define setmax(a, b) (a = max(a, b))
#define LOG2(x) (log(x) / log(2))
#define XX first.first
#define XY first.second
#define YX second.first
#define YY second.second

using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<double, double> Pd;
typedef pair<int, int> Pi;
typedef pair<LL, LL> Pl;

ULL countSimilarPairs(const std::vector<int> &v) {
	int len = v.size();
	map<int, int> m;
	for (int i = 0; i < len; ++i) {
		auto itr = m.find(v[i]);
		if (itr == m.end()) {
			m[v[i]] = 1;
		} else {
			itr->second++;
		}
	}
	ULL ans = 0;
	for (auto e : m) {
		if (e.second > 1) {
			ULL x = e.second;
			ans += x * (x - 1) / 2;
		}
	}
	return ans;
}

long long CountSimilarPairs(std::vector<int> B, std::vector<int> T, std::vector<int> G) {
	int len = B.size();
	ULL ans = countSimilarPairs(B) + countSimilarPairs(T) + countSimilarPairs(G);
	vector<int> v;
	v.resize(len);
	for (int i = 0; i < len; ++i) {
		v[i] = B[i] * 10000 + T[i] * 100 + G[i];
	}
	ans += countSimilarPairs(v);
	for (int i = 0; i < len; ++i) {
		v[i] = B[i] * 100 + T[i];
	}
	ans -= countSimilarPairs(v);
	for (int i = 0; i < len; ++i) {
		v[i] = B[i] * 100 + G[i];
	}
	ans -= countSimilarPairs(v);
	for (int i = 0; i < len; ++i) {
		v[i] = G[i] * 100 + T[i];
	}
	ans -= countSimilarPairs(v);
	return ans;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 9 ms 512 KB Output is correct

Subtask #2
73.0 / 73.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 9 ms 512 KB Output is correct
11 Correct 15 ms 768 KB Output is correct
12 Correct 21 ms 1280 KB Output is correct
13 Correct 102 ms 4468 KB Output is correct
14 Correct 143 ms 6260 KB Output is correct
15 Correct 249 ms 9192 KB Output is correct
16 Correct 79 ms 5996 KB Output is correct
17 Correct 143 ms 5988 KB Output is correct
18 Correct 273 ms 10596 KB Output is correct
19 Correct 472 ms 14444 KB Output is correct
20 Correct 424 ms 14436 KB Output is correct