Submission #208417

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
208417	2020-03-11T07:40:43 Z	Atalasion	PIN (CEOI10_pin)	C++14	70 / 100	336 ms	10492 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 <= 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

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	6776 KB	Output is correct
2	Correct	17 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	122 ms	8576 KB	Output is correct
6	Correct	124 ms	8568 KB	Output is correct
7	Correct	103 ms	8184 KB	Output is correct
8	Correct	134 ms	8828 KB	Output is correct
9	Correct	213 ms	10104 KB	Output is correct
10	Correct	242 ms	10492 KB	Output is correct
11	Correct	130 ms	8696 KB	Output is correct
12	Correct	227 ms	10236 KB	Output is correct
13	Correct	145 ms	8952 KB	Output is correct
14	Incorrect	133 ms	8844 KB	Output isn't correct
15	Incorrect	228 ms	10256 KB	Output isn't correct
16	Correct	208 ms	9208 KB	Output is correct
17	Correct	314 ms	10488 KB	Output is correct
18	Incorrect	238 ms	9592 KB	Output isn't correct
19	Incorrect	277 ms	10104 KB	Output isn't correct
20	Incorrect	336 ms	10488 KB	Output isn't correct