oj.uz

답안 #208422

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208422 2020-03-11T07:48:35 Z Atalasion PIN (CEOI10_pin) C++14
100 / 100
 313 ms 10616 KB 
//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

# 결과 실행 시간 메모리 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