Submission #208422

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
208422	2020-03-11T07:48:35 Z	Atalasion	PIN (CEOI10_pin)	C++14	100 / 100	313 ms	10616 KB

pin

//khodaya khodet komak kon
#include <bits/stdc++.h>
 
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")
#define int long long
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
const int N = 200000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;
 
int n, d, ted[5];
map<string, int> mp;
string s[N];
 
ll nCr(ll x, ll y){
	ll res = 1;
	for (int i = 1; i <= x; i++){
		res = res * i;
	}
	for (int i = 1; i <= y; i++) res /= i;
	for (int i = 1; i <= x - y; i++) res /= i;
	return res;
}
 
int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> d;
	d = 4 - d;
	for (int i = 1; i <= n; i++){
		cin >> s[i];
	}	
	for (int mask = 0; mask < (1 << 4); mask++){
		mp.clear();
		for (int i = 1; i <= n; i++){
			string res = "";
			int cnt = 0;
			for (int j = 0; j < 4; j++){
				if (mask & (1 << j)) res += s[i][j], cnt++;
				else res += "?";
			}
		//	cout << res << '\n';
			ted[cnt] += mp[res];
			mp[res] ++;
		}
	}
	
//	cout << nCr(3, 0) << ' ' << nCr(3, 1) << ' ' << nCr(3, 2) << '\n';
	//cout << ted[0] << ' ' << ted[1] < 
	for (int i = 3; i >= 0; i--){
		for (int j = i + 1; j <= 3; j++){
			ted[i] -= ted[j] *  nCr(j, i);
		}
	}
 
	cout << ted[d];
 
 
 
 
 
 
 
 
	return 0;
}

Compilation message

pin.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise ("ofast")
 
pin.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise("unroll-loops")

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	6648 KB	Output is correct
2	Correct	16 ms	6776 KB	Output is correct
3	Correct	14 ms	6648 KB	Output is correct
4	Correct	103 ms	8184 KB	Output is correct
5	Correct	124 ms	8568 KB	Output is correct
6	Correct	125 ms	8568 KB	Output is correct
7	Correct	104 ms	8180 KB	Output is correct
8	Correct	136 ms	8696 KB	Output is correct
9	Correct	219 ms	10120 KB	Output is correct
10	Correct	242 ms	10488 KB	Output is correct
11	Correct	132 ms	8696 KB	Output is correct
12	Correct	233 ms	10352 KB	Output is correct
13	Correct	146 ms	8952 KB	Output is correct
14	Correct	136 ms	8696 KB	Output is correct
15	Correct	239 ms	10360 KB	Output is correct
16	Correct	209 ms	9208 KB	Output is correct
17	Correct	309 ms	10488 KB	Output is correct
18	Correct	242 ms	9720 KB	Output is correct
19	Correct	277 ms	10028 KB	Output is correct
20	Correct	313 ms	10616 KB	Output is correct