CSES - KILO 2017 4/5 - Results
Submission details
Task:Dice Cup
Sender:Tuukka Korhonen
Submission time:2017-09-26 18:51:37 +0300
Language:C++
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:62:18: error: no matching function for call to 'max(int&, __gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type&)'
   ma=max(ma, c[i]);
                  ^
input/code.cpp:62:18: note: candidates are:
In file included from /usr/include/c++/4.8/bits/char_traits.h:39:0,
                 from /usr/include/c++/4.8/ios:40,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/sstream:38,
                 from /usr/include/c++/4.8/complex:45,
                 from /usr/include/c++/4.8/ccomplex:38,
                 from /usr/include/x86_64-linux-gnu/c++/4.8/bits/stdc++.h:52,
                 from input/code.cpp:1:
/usr/include/c++/4.8/bits/stl_algobase.h:216:5: note: template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.8/bits/stl_algobase.h:216:5: note:   template argument deduction/substitution failed...

Code

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef complex<ld> co;
const ld PI=atan2((ld)0, (ld)-1);
void fft(vector<co>&a, int n, int k) {
	vector<co> ww(n);
	ww[1]=co(1, 0);
	for (int t=0;t<k-1;t++) {
		co c=polar((ld)1, PI/n*(1<<(k-1-t)));
		int p2=(1<<t),p3=p2*2;
		for (int j=p2;j<p3;j++) ww[j*2+1]=(ww[j*2]=ww[j])*c;
	}
	for (int i=0;i<n;i++) {
		int u=0;
		for (int j=1;j<n;j*=2) {u*=2;if (i&j) u++;}
		if (i<u) swap(a[i], a[u]);
	}
	for (int l=1;l<n;l*=2) {
		for (int i=0;i<n;i+=l) {
			for (int it=0,j=i+l,w=l;it<l;it++,i++,j++) {
				co t=a[j]*ww[w++];
				a[j]=a[i]-t;
				a[i]=a[i]+t;
			}
		}
	}
}
vector<ll> conv(const vector<ll>& a, const vector<ll>& b) {
	int as=a.size(), bs=b.size();
	if (as*bs==0) return {};
	int k=0;
	while ((1<<k)<as+bs-1) k++;
	int n=1<<k;
	vector<co> c(n+1);
	for (int i=0;i<n;i++) {
		if (i<as) c[i]=a[i];
		if (i<bs) c[i]={c[i].real(), (ld)b[i]};
	}
	fft(c, n, k);
	c[n]=c[0];
	for (int i=0;i<=n-i;i++) {
		c[i]=conj(c[i]*c[i]-conj(c[n-i]*c[n-i]))*co(0,(ld)1/n/4);
		c[n-i]=conj(c[i]);
	}
	fft(c, n, k);
	vector<ll> r(as+bs-1);
	for (int i=0;i<as+bs-1;i++) r[i]=round(c[i].real());
	return r;
}
int main() {
	int n,m;
	cin>>n>>m;
	vector<ll> a(n+1);
	vector<ll> b(m+1);
	for (int i=1;i<=n;i++) a[i]=1;
	for (int i=1;i<=m;i++) b[i]=1;
	auto c=conv(a, b);
	int ma=0;
	for (int i=0;i<(int)c.size();i++){
		ma=max(ma, c[i]);
	}
	for (int i=0;i<(int)c.size();i++){
		if (c[i]==ma) cout<<i<<endl;
	}
}