Submission #487758

#	Time	Username	Problem	Language	Result	Execution time	Memory
487758		errorgorn	Set (COCI21_set)	C++17	110 / 110	148 ms	15444 KiB

Main

#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 (stderr)

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);
      |  ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 70 / 70