oj.uz

Submission #148851

# Submission time Handle Problem Language Result Execution time Memory
148851 2019-09-01T05:15:23 Z ProofByTLE(#3614, Mahotsukai, McDic, Redux) FunctionCup Museum (FXCUP4_museum) C++17
100 / 100
 94 ms 13188 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

#define EPS 1e-14
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define INFLL (ll)1e18 //Long long infinity
#define INF (int)1e9 //Int infinity
#define MX 100005

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vd> vvd;
typedef vector<string> vstr;

#define us unordered_set
#define um unordered_map
#define bs bitset

#define RANGE(i,a,b,d) for (int i=min((int)a,(int)b); i<max((int)a,(int)b); i+=d)
#define RRANGE(i,a,b,d) for (int i=max((int)a,(int)b); i>min((int)a,(int)b); i+=d)
#define FOR(i,a,b) RANGE(i,a,b,1)
#define RFOR(i,a,b) RRANGE(i,a,b,-1)
#define REP(i,s) FOR(i,0,s)
#define RREP(i,s) RFOR(i,s-1,-1)
#define FORIT(it,l) for (auto it = l.begin(); it != l.end(); it++)
#define EACH(x,v) for (auto &x : v)

#define sz(x) (int)(x).size()
#define len(x) (int)sizeof(x)/sizeof(*x)
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define contains(m,x) (m.find(x) != m.end()) // check if an element in a map
#define isIn(S, s) (S.find(s) != string::npos) // check if substring

#define pv(v) EACH(x, v) cout << x << " "; cout << endl; // print vector/array
#define pvv(vv) EACH(xx, vv){pv(xx);} // print 2-d vector/2-d array
#define pm(m) EACH(x, m) cout << x.F << ":" << x.S << " "; cout << endl; //print map/lookup table

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

namespace std{
  // Used for hashing pair
  template <> struct hash<pi>{
    size_t operator()(const pi&x)const{
      ll P=38923, Q=109797901;
      return (size_t)((x.F*P+x.S)%Q);
    }
  };
};

// This is min queue
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

template <typename T>
void print(T t){
  cout << t << endl;
}

//Python style printing
template<typename T, typename... Args>
void print(T t, Args... args){
  cout << t << " ";
  print(args...);
}

ll CountSimilarPairs(vi B, vi T, vi G) {
  int n = sz(B);
  vl a(100, 0), b(100, 0), c(100, 0), d(100 * 100, 0), e(100 * 100, 0), f(100 * 100, 0), g(100 * 100 * 100, 0);
  REP(i, n) B[i]--, T[i]--, G[i]--;
  REP(i, n) {
    a[B[i]]++;
    b[T[i]]++;
    c[G[i]]++;
    d[B[i]*100+T[i]]++;
    e[B[i]*100+G[i]]++;
    f[G[i]*100+T[i]]++;
    g[B[i]*10000+G[i]*100+T[i]]++;
  }
  ll sol = 0;
  REP(i, 100) sol += a[i] * (a[i]-1) + b[i]*(b[i]-1) + c[i]*(c[i]-1);
  REP(i, 10000) sol -= (d[i]*(d[i]-1) + e[i]*(e[i]-1) + f[i]*(f[i]-1));
  REP(i, 1000000) sol += g[i]*(g[i]-1);
  sol/=2;
  return sol;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8448 KB Output is correct
2 Correct 11 ms 8448 KB Output is correct
3 Correct 10 ms 8448 KB Output is correct
4 Correct 12 ms 8448 KB Output is correct
5 Correct 11 ms 8448 KB Output is correct
6 Correct 12 ms 8448 KB Output is correct
7 Correct 12 ms 8448 KB Output is correct
8 Correct 12 ms 8448 KB Output is correct
9 Correct 12 ms 8576 KB Output is correct
10 Correct 12 ms 8448 KB Output is correct

Subtask #2
73.0 / 73.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8448 KB Output is correct
2 Correct 11 ms 8448 KB Output is correct
3 Correct 10 ms 8448 KB Output is correct
4 Correct 12 ms 8448 KB Output is correct
5 Correct 11 ms 8448 KB Output is correct
6 Correct 12 ms 8448 KB Output is correct
7 Correct 12 ms 8448 KB Output is correct
8 Correct 12 ms 8448 KB Output is correct
9 Correct 12 ms 8576 KB Output is correct
10 Correct 12 ms 8448 KB Output is correct
11 Correct 13 ms 8576 KB Output is correct
12 Correct 28 ms 9216 KB Output is correct
13 Correct 34 ms 9724 KB Output is correct
14 Correct 47 ms 10352 KB Output is correct
15 Correct 61 ms 11396 KB Output is correct
16 Correct 86 ms 13160 KB Output is correct
17 Correct 83 ms 13188 KB Output is correct
18 Correct 88 ms 13188 KB Output is correct
19 Correct 94 ms 13156 KB Output is correct
20 Correct 92 ms 13164 KB Output is correct