# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
487758 |
2021-11-16T14:32:22 Z |
errorgorn |
Set (COCI21_set) |
C++17 |
|
148 ms |
15444 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
mt19937 rng(123123);
#define ld double
#define C complex<ld>
const ld TAU=acosl(0)*4;
const C a=1,b=exp(complex<ld>(0,1.0/3)*TAU),c=exp(complex<ld>(0,2.0/3)*TAU);
C fwht[3][3]={
{a,a,a},
{a,b,c},
{a,c,b}
};
C ifwht[3][3]={
{a,a,a},
{a,c,b},
{a,b,c}
};
int n,k;
C arr[531450];
const int THREE[]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441};
C temp[3];
const C three={3,0};
int main(){
scanf("%d%d",&n,&k);
rep(x,0,n){
getchar_unlocked();
int val=0;
rep(y,0,k){
val+=THREE[y]*(getchar_unlocked()-'1');
}
arr[val]={1,0};
}
for (int step = 1; step < THREE[k]; step *= 3) {
for (int i = 0; i < THREE[k]; i += 3 * step) rep(j,i,i+step) {
temp[0]=arr[j]*fwht[0][0]+arr[j+step]*fwht[0][1]+arr[j+2*step]*fwht[0][2];
temp[1]=arr[j]*fwht[1][0]+arr[j+step]*fwht[1][1]+arr[j+2*step]*fwht[1][2];
temp[2]=arr[j]*fwht[2][0]+arr[j+step]*fwht[2][1]+arr[j+2*step]*fwht[2][2];
rep(i,0,3) arr[j+i*step]=temp[i];
}
}
rep(x,0,THREE[k]) arr[x]=arr[x]*arr[x]*arr[x];
for (int step = 1; step < THREE[k]; step *= 3) {
for (int i = 0; i < THREE[k]; i += 3 * step) rep(j,i,i+step) {
temp[0]=arr[j]*ifwht[0][0]+arr[j+step]*ifwht[0][1]+arr[j+2*step]*ifwht[0][2];
temp[1]=arr[j]*ifwht[1][0]+arr[j+step]*ifwht[1][1]+arr[j+2*step]*ifwht[1][2];
temp[2]=arr[j]*ifwht[2][0]+arr[j+step]*ifwht[2][1]+arr[j+2*step]*ifwht[2][2];
rep(i,0,3) arr[j+i*step]=temp[i]/three;
}
}
//cout<<(arr[0].real())-n<<endl;
ll ans=floor(((arr[0].real())-n)/6+0.5);
cout<<ans<<endl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d%d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
304 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
0 ms |
208 KB |
Output is correct |
7 |
Correct |
0 ms |
208 KB |
Output is correct |
8 |
Correct |
0 ms |
208 KB |
Output is correct |
9 |
Correct |
0 ms |
276 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
11 |
Correct |
0 ms |
312 KB |
Output is correct |
12 |
Correct |
0 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
208 KB |
Output is correct |
14 |
Correct |
0 ms |
208 KB |
Output is correct |
15 |
Correct |
0 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
304 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
0 ms |
208 KB |
Output is correct |
7 |
Correct |
0 ms |
208 KB |
Output is correct |
8 |
Correct |
0 ms |
208 KB |
Output is correct |
9 |
Correct |
0 ms |
276 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
11 |
Correct |
0 ms |
312 KB |
Output is correct |
12 |
Correct |
0 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
208 KB |
Output is correct |
14 |
Correct |
0 ms |
208 KB |
Output is correct |
15 |
Correct |
0 ms |
208 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
0 ms |
208 KB |
Output is correct |
21 |
Correct |
0 ms |
208 KB |
Output is correct |
22 |
Correct |
0 ms |
208 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
336 KB |
Output is correct |
27 |
Correct |
1 ms |
336 KB |
Output is correct |
28 |
Correct |
0 ms |
208 KB |
Output is correct |
29 |
Correct |
0 ms |
208 KB |
Output is correct |
30 |
Correct |
0 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
304 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
0 ms |
208 KB |
Output is correct |
6 |
Correct |
0 ms |
208 KB |
Output is correct |
7 |
Correct |
0 ms |
208 KB |
Output is correct |
8 |
Correct |
0 ms |
208 KB |
Output is correct |
9 |
Correct |
0 ms |
276 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
11 |
Correct |
0 ms |
312 KB |
Output is correct |
12 |
Correct |
0 ms |
208 KB |
Output is correct |
13 |
Correct |
1 ms |
208 KB |
Output is correct |
14 |
Correct |
0 ms |
208 KB |
Output is correct |
15 |
Correct |
0 ms |
208 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
0 ms |
208 KB |
Output is correct |
21 |
Correct |
0 ms |
208 KB |
Output is correct |
22 |
Correct |
0 ms |
208 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
336 KB |
Output is correct |
27 |
Correct |
1 ms |
336 KB |
Output is correct |
28 |
Correct |
0 ms |
208 KB |
Output is correct |
29 |
Correct |
0 ms |
208 KB |
Output is correct |
30 |
Correct |
0 ms |
208 KB |
Output is correct |
31 |
Correct |
95 ms |
8612 KB |
Output is correct |
32 |
Correct |
98 ms |
8600 KB |
Output is correct |
33 |
Correct |
98 ms |
8528 KB |
Output is correct |
34 |
Correct |
144 ms |
15444 KB |
Output is correct |
35 |
Correct |
1 ms |
336 KB |
Output is correct |
36 |
Correct |
0 ms |
208 KB |
Output is correct |
37 |
Correct |
1 ms |
336 KB |
Output is correct |
38 |
Correct |
124 ms |
14664 KB |
Output is correct |
39 |
Correct |
107 ms |
10108 KB |
Output is correct |
40 |
Correct |
121 ms |
14616 KB |
Output is correct |
41 |
Correct |
95 ms |
9116 KB |
Output is correct |
42 |
Correct |
148 ms |
14504 KB |
Output is correct |
43 |
Correct |
1 ms |
208 KB |
Output is correct |
44 |
Correct |
0 ms |
208 KB |
Output is correct |
45 |
Correct |
0 ms |
208 KB |
Output is correct |