I am currently solving this problem , and I get TLE on three test cases due to the slow nature of maps with vectors as keys.
Does anyone know why it’s slow?
#include <bits/stdc++.h>
using namespace std;
using ll = int;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
#define forn(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, a, b) for(ll i = a; i < b; i++)
#define rofn(i, n) for(ll i = n; i >= 0; i--)
#define ROF(i, a, b) for(ll i = a; i >= b; i--)
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("cowpatibility.in", "r", stdin);
freopen("cowpatibility.out", "w", stdout);
long long n; cin >> n;
map<vl, ll> mp;
long long ans = 0;
forn(i, n){
vl flavors(5);
forn(i, 5) cin >> flavors[i];
sor(flavors);
forn(j, 32){
vl cur;
forn(k, 5){
if(j & (1 << k)){
cur.pb(flavors[k]);
}
}
if(cur.size() & 1){
ans += mp[cur];
} else {
ans -= mp[cur];
}
if(cur.size()) mp[cur]++;
}
}
cout << (n * (n - 1) / 2) - ans << endl;
}
I even tried converting from long long to int…
Benq
July 27, 2022, 12:37am
#2
It’s generally the case that operations on vectors with size bounded above by a constant will be a little slower than the corresponding operations on fixed-size arrays.
Looks like the time limit was set so tight that the analysis solution doesn’t even pass USACO Monthlies )
To pass comfortably below the time limit you’ll probably need to do at least one of the following:
Replace the map in the analysis solution with a sorted vector.
Use some sort of hashing (ex. XOR Hashing [TUTORIAL] - Codeforces ).
Some solutions that work:
Solution 1
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ii = pair<ll, ll>;
#define fastIO ios::sync_with_stdio(0); cin.tie(0);
#define fi first
#define se second
#define pb push_back
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define MASK(x) 1ll << (x)
template<class X, class Y>
bool minimize(X &x, const Y &y) {
X eps = 1e-9;
if (x > y + eps) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return true;
} else return false;
}
const int N = 5e4 + 7, M = 1e6 + 7, oo = 1e9 + 7, MOD = 1e9 + 7;
int n, a[6], cnt[6];
signed main() {
fastIO;
freopen("cowpatibility.in", "r", stdin);
freopen("cowpatibility.out", "w", stdout);
cin >> n; vector<int> x; x.reserve(5);
vector<vector<int>> dp;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 5; j++)
cin >> a[j];
sort(a, a + 5);
for (int m = 1; m < (1 << 5); m++) {
x.clear();
for (int j = 0; j < 5; j++)
if (getBit(m, j)) x.pb(a[j]);
dp.push_back(x);
}
}
sort(begin(dp), end(dp));
ll ans = 1ll * n * (n - 1) / 2;
for (int i = 0; i < size(dp); ) {
int j = i;
while (i < size(dp) && dp.at(i) == dp.at(j)) ++i;
int dif = i-j;
if (sz(dp.at(j))&1) ans -= 1ll*dif*(dif-1)/2;
else ans += 1ll*dif*(dif-1)/2;
}
cout << ans;
}
Solution 2
#include <bits/stdc++.h>
using namespace std;
using ll = int;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
#define forn(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, a, b) for(ll i = a; i < b; i++)
#define rofn(i, n) for(ll i = n; i >= 0; i--)
#define ROF(i, a, b) for(ll i = a; i >= b; i--)
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("cowpatibility.in", "r", stdin);
freopen("cowpatibility.out", "w", stdout);
mt19937_64 rng;
long long n; cin >> n;
vector<uint64_t> hashes(1000001);
for (int i = 1; i <= 1000000; ++i) hashes[i] = rng();
unordered_map<uint64_t, ll> mp;
long long ans = 0;
forn(i, n){
vl flavors(5);
forn(i, 5) cin >> flavors[i];
sor(flavors);
forn(j, 32){
uint64_t cur = 0;
int cnt = 0;
forn(k, 5){
if(j & (1 << k)){
cur ^= hashes[flavors[k]];
++cnt;
}
}
if(cnt & 1){
ans += mp[cur];
} else {
ans -= mp[cur];
}
if(cnt) mp[cur]++;
}
}
cout << (n * (n - 1) / 2) - ans << endl;
}
1 Like
Same with the only user-submitted solution on USACO Guide … (