Submission #580440

#	Time	Username	Problem	Language	Result	Execution time	Memory
580440		juggernaut	Lottery (CEOI18_lot)	C++14	65 / 100	565 ms	15900 KiB

lot

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n,l;
int a[10005];
int b[2005][2005];
map<ll,int>mp;
ll c[10005];
int main(){
	scanf("%d%d",&n,&l);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	if(n<=2000){
		for(int i=1;i+l-1<=n;i++){
			for(int j=1;j+l-1<=n;j++){
				int cnt=0;
				for(int k=0;k<l;k++)if(a[i+k]!=a[j+k])cnt++;
				b[i][cnt]++;
			}
			for(int j=1;j<2005;j++)b[i][j]+=b[i][j-1];
		}
		int q;
		scanf("%d",&q);
		while(q--){
			int x;
			scanf("%d",&x);
			for(int i=1;i+l-1<=n;i++)printf("%d ",b[i][x]-1);
			puts("");
		}
		return 0;
	}
	const ll P=1e9+7;
	const ll mod=1e9+9;
	const ll P2=1e9+9;
	const ll mod2=(1<<29)-1;
	for(int i=1;i+l-1<=n;i++){
		ll pw=1;
		ll hsh=0;
		ll pw2=1;
		ll hsh2=0;
		for(int j=0;j<l;j++){
			hsh+=(a[i+j]*pw)%mod;
			hsh%=mod;
			pw*=P;
			pw%=mod;
			
			hsh2+=(a[i+j]*pw2)%mod2;
			hsh2%=mod2;
			pw2*=P2;
			pw2%=mod2;
		}
		mp[hsh*P+hsh2]++;
		c[i]=hsh*P+hsh2;
	}
	for(int i=1;i+l-1<=n;i++)printf("%d ",mp[c[i]]-1);
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%d%d",&n,&l);
      |  ~~~~~^~~~~~~~~~~~~~
lot.cpp:27:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  for(int i=1;i<=n;i++)scanf("%d",&a[i]);
      |                       ~~~~~^~~~~~~~~~~~
lot.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d",&q);
      |   ~~~~~^~~~~~~~~
lot.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20