oj.uz

Submission #151226

# Submission time Handle Problem Language Result Execution time Memory
151226 2019-09-02T09:22:26 Z dongwon0427 FunctionCup Museum (FXCUP4_museum) C++17
100 / 100
 262 ms 24216 KB 
#include "museum.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
    int a,b,c;
    bool operator < (const node &n) const {
        if(a == n.a) {
            if(b == n.b) return c < n.c;
            return b < n.b;
        }
        return a < n.a;
    }
    bool operator == (const node &n) const {
        return a == n.a && b==n.b && c==n.c;
    }
};

vector<node> a,b,c,d,e,f,g;
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++) {
        a.push_back({B[i],-1,-1});
	}
	for(int i=0;i<n;i++) {
        b.push_back({-1,T[i],-1});
	}
	for(int i=0;i<n;i++) {
        c.push_back({-1,-1,G[i]});
	}
	for(int i=0;i<n;i++) {
        d.push_back({B[i],T[i],-1});
	}
	for(int i=0;i<n;i++) {
        e.push_back({B[i],-1,G[i]});
	}
	for(int i=0;i<n;i++) {
        f.push_back({-1,T[i],G[i]});
	}
	for(int i=0;i<n;i++) {
        g.push_back({B[i],T[i],G[i]});
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());
	sort(d.begin(), d.end());
	sort(e.begin(), e.end());
	sort(f.begin(), f.end());
	sort(g.begin(), g.end());

	ll ret = 0;
	ll cnt = 0;
	node bf = {-1,-1,-1};
	for(int i=0;i<n;i++) {
        if(bf == a[i]) {
            cnt++;
        } else {
            ret += cnt * (cnt-1) / 2;
            cnt = 1;
            bf = a[i];
        }
	}
	ret += cnt * (cnt-1) / 2;

	cnt = 0;
	bf = {-1,-1,-1};
	for(int i=0;i<n;i++) {
        if(bf == b[i]) {
            cnt++;
        } else {
            ret += cnt * (cnt-1) / 2;
            cnt = 1;
            bf = b[i];
        }
	}
	ret += cnt * (cnt-1) / 2;

	cnt = 0;
	bf = {-1,-1,-1};
	for(int i=0;i<n;i++) {
        if(bf == c[i]) {
            cnt++;
        } else {
            ret += cnt * (cnt-1) / 2;
            cnt = 1;
            bf = c[i];
        }
	}
	ret += cnt * (cnt-1) / 2;

	cnt = 0;
	bf = {-1,-1,-1};
	for(int i=0;i<n;i++) {
        if(bf == d[i]) {
            cnt++;
        } else {
            ret -= cnt * (cnt-1) / 2;
            cnt = 1;
            bf = d[i];
        }
	}
	ret -= cnt * (cnt-1) / 2;

	cnt = 0;
	bf = {-1,-1,-1};
	for(int i=0;i<n;i++) {
        if(bf == e[i]) {
            cnt++;
        } else {
            ret -= cnt * (cnt-1) / 2;
            cnt = 1;
            bf = e[i];
        }
	}
	ret -= cnt * (cnt-1) / 2;

	cnt = 0;
	bf = {-1,-1,-1};
	for(int i=0;i<n;i++) {
        if(bf == f[i]) {
            cnt++;
        } else {
            ret -= cnt * (cnt-1) / 2;
            cnt = 1;
            bf = f[i];
        }
	}
	ret -= cnt * (cnt-1) / 2;

	cnt = 0;
	bf = {-1,-1,-1};
	for(int i=0;i<n;i++) {
        if(bf == g[i]) {
            cnt++;
        } else {
            ret += cnt * (cnt-1) / 2;
            cnt = 1;
            bf = g[i];
        }
	}
	ret += cnt * (cnt-1) / 2;
	return ret;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 252 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 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct

Subtask #2
73.0 / 73.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 252 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 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 8 ms 1144 KB Output is correct
12 Correct 30 ms 4004 KB Output is correct
13 Correct 71 ms 7128 KB Output is correct
14 Correct 105 ms 10704 KB Output is correct
15 Correct 155 ms 14660 KB Output is correct
16 Correct 164 ms 24216 KB Output is correct
17 Correct 228 ms 24140 KB Output is correct
18 Correct 251 ms 24176 KB Output is correct
19 Correct 260 ms 24172 KB Output is correct
20 Correct 262 ms 24172 KB Output is correct