Submission #208418

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
208418	2020-03-11T07:42:26 Z	Atalasion	PIN (CEOI10_pin)	C++14	70 / 100	319 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 = 1; 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 <= 4; 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

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	6648 KB	Output is correct
2	Correct	16 ms	6648 KB	Output is correct
3	Incorrect	14 ms	6648 KB	Output isn't correct
4	Correct	101 ms	8184 KB	Output is correct
5	Correct	123 ms	8568 KB	Output is correct
6	Correct	126 ms	8568 KB	Output is correct
7	Correct	99 ms	8184 KB	Output is correct
8	Correct	137 ms	8696 KB	Output is correct
9	Correct	214 ms	10104 KB	Output is correct
10	Correct	237 ms	10488 KB	Output is correct
11	Correct	130 ms	8696 KB	Output is correct
12	Correct	224 ms	10232 KB	Output is correct
13	Correct	146 ms	8952 KB	Output is correct
14	Incorrect	132 ms	8696 KB	Output isn't correct
15	Incorrect	230 ms	10252 KB	Output isn't correct
16	Correct	208 ms	9208 KB	Output is correct
17	Correct	319 ms	10488 KB	Output is correct
18	Incorrect	249 ms	9720 KB	Output isn't correct
19	Incorrect	275 ms	10104 KB	Output isn't correct
20	Incorrect	314 ms	10616 KB	Output isn't correct