oj.uz

Submission #149430

# Submission time Handle Problem Language Result Execution time Memory
149430 2019-09-01T06:28:00 Z 티셔츠 콜렉터(#3632, yoni, jisunchae, jsg1504) FunctionCup Museum (FXCUP4_museum) C++17
100 / 100
 181 ms 8932 KB 
#include "museum.h"
#include <algorithm>

struct data {
	int b, t, g;
};
bool cmp1(const data& a, const data& b) {
	if (a.b < b.b) return true;
	if (a.b == b.b) {
		if (a.t < b.t) return true;
		if (a.t == b.t) return a.g < b.g;
	}
	return false;
}
bool cmp2(const data& a, const data& b) {
	if (a.t < b.t) return true;
	if (a.t == b.t) {
		if (a.g < b.g) return true;
		if (a.g == b.g) return a.b < b.b;
	}
	return false;
}
bool cmp3(const data& a, const data& b) {
	if (a.g < b.g) return true;
	if (a.g == b.g) {
		if (a.b < b.b) return true;
		if (a.b == b.b) return a.t < b.t;
	}
	return false;
}

std::vector<data> V;
long long CountSimilarPairs(std::vector<int> B, std::vector<int> T, std::vector<int> G) {
	int N = B.size();
	for (int i=0; i<N; i++) {
		V.push_back({B[i], T[i], G[i]});
	}
	long long res = 0;
	std::sort(V.begin(), V.end(), cmp1);
	long long cnt1=1, cnt2=1, cnt3=1;
	for (int i=1; i<N; i++) {
		if (V[i].b == V[i-1].b) {
			cnt1++;
			if (V[i].t == V[i-1].t) {
				cnt2++;
				if (V[i].g == V[i-1].g) {
					cnt3++;
				} else {
					res += cnt3*(cnt3-1)/2;
					cnt3=1;
				}
			} else {
				res -= cnt2*(cnt2-1)/2;
				res += cnt3*(cnt3-1)/2;
				cnt2=cnt3=1;
			}
		} else {
			res += cnt1*(cnt1-1)/2;
			res -= cnt2*(cnt2-1)/2;
			res += cnt3*(cnt3-1)/2;
			cnt1=cnt2=cnt3=1;
		}
	}
	res += cnt1*(cnt1-1)/2;
	res -= cnt2*(cnt2-1)/2;
	res += cnt3*(cnt3-1)/2;
	cnt1=cnt2=cnt3=1;
	std::sort(V.begin(), V.end(), cmp2);
	for (int i=1; i<N; i++) {
		if (V[i].t == V[i-1].t) {
			cnt1++;
			if (V[i].g == V[i-1].g) {
				cnt2++;
			} else {
				res -= cnt2*(cnt2-1)/2;
				cnt2=1;
			}
		} else {
			res += cnt1*(cnt1-1)/2;
			res -= cnt2*(cnt2-1)/2;
			cnt1=cnt2=1;
		}
	}
	res += cnt1*(cnt1-1)/2;
	res -= cnt2*(cnt2-1)/2;
	cnt1=cnt2=1;
	std::sort(V.begin(), V.end(), cmp3);
	cnt1=1, cnt2=1, cnt3=1;
	for (int i=1; i<N; i++) {
		if (V[i].g == V[i-1].g) {
			cnt1++;
			if (V[i].b == V[i-1].b) {
				cnt2++;
			} else {
				res -= cnt2*(cnt2-1)/2;
				cnt2=1;
			}
		} else {
			res += cnt1*(cnt1-1)/2;
			res -= cnt2*(cnt2-1)/2;
			cnt1=cnt2=1;
		}
	}
	res += cnt1*(cnt1-1)/2;
	res -= cnt2*(cnt2-1)/2;

	return res;
}

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 128 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 128 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 8 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 128 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 128 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 6 ms 256 KB Output is correct
8 Correct 6 ms 256 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 8 ms 512 KB Output is correct
11 Correct 10 ms 640 KB Output is correct
12 Correct 22 ms 1600 KB Output is correct
13 Correct 52 ms 2544 KB Output is correct
14 Correct 78 ms 4204 KB Output is correct
15 Correct 111 ms 5096 KB Output is correct
16 Correct 103 ms 8932 KB Output is correct
17 Correct 133 ms 8932 KB Output is correct
18 Correct 177 ms 8928 KB Output is correct
19 Correct 181 ms 8932 KB Output is correct
20 Correct 178 ms 8928 KB Output is correct