Submission #617194

#	Time	Username	Problem	Language	Result	Execution time	Memory
617194		yutabi	Lottery (CEOI18_lot)	C++14	20 / 100	7 ms	1364 KiB

lot

#include <bits/stdc++.h>
using namespace std;


#define MOD 1000000007
#define pb push_back


typedef long long ll;


int n;

int length;


vector <int> s;


vector <vector <int> > k;

vector <int> u;

int ans;

int q;


map <pair <ll,ll> ,int> mp;


ll pw;


int main()
{
	scanf("%d %d",&n,&length);

	pw=1;

	for(int i=0;i<length-1;i++)
	{
		pw*=46853;
		pw%=MOD;
	}

	s.resize(n);
	k=vector <vector <int> > (n);
	u=vector <int> (n,0);

	for(int i=0;i<n;i++)
	{
		scanf(" %d",&s[i]);
	}

	/*for(int i=0;i<n;i++)
	{
		int l=s[i];

		for(int j=0;j<n;j++)
		{
			if(i==j)
			{
				continue;
			}

			if(min(i,j)+n-max(i,j)<length)
			{
				continue;
			}

			if(s[i]==s[j])
			{
				k[i].pb(n+j-i);
			}
		}
	}*/

	//printf("\n%d\n\n",k[0][0]);

	scanf("	%d",&q);

	int asdasd;

	for(int i=0;i<q;i++)
	{
		scanf(" %d",&asdasd);
	}

	ll hash=0;
	ll hash2=0;

	for(int i=0;i<length-1;i++)
	{
		hash*=46853;
		hash%=MOD;
		hash2*=46853;
		hash2%=MOD;

		ll temp=s[i];
		temp*=2147867;
		temp%=MOD;
		temp+=843469;
		temp%=MOD;

		hash+=temp;
		hash%=MOD;

		temp=s[i];
		temp*=54785623;
		temp%=MOD;
		temp+=235346;
		temp%=MOD;

		hash2+=temp;
		hash2%=MOD;
	}

	vector <pair <ll,ll> > hashes;

	for(int i=length-1;i<n;i++)
	{
		hash*=46853;
		hash%=MOD;
		hash2*=46853;
		hash2%=MOD;

		ll temp=s[i];
		temp*=2147867;
		temp%=MOD;
		temp+=843469;
		temp%=MOD;

		hash+=temp;
		hash%=MOD;

		temp=s[i];
		temp*=54785623;
		temp%=MOD;
		temp+=235346;
		temp%=MOD;

		hash2+=temp;
		hash2%=MOD;

		hashes.pb(make_pair(hash,hash2));

		mp[make_pair (hash,hash2)]++;

		temp=s[i-length+1];
		temp*=2147867;
		temp%=MOD;
		temp+=843469;
		temp%=MOD;
		temp*=pw;
		temp%=MOD;

		hash-=temp;
		hash+=MOD;
		hash%=MOD;

		temp=s[i-length+1];
		temp*=54785623;
		temp%=MOD;
		temp+=235346;
		temp%=MOD;
		temp*=pw;
		temp%=MOD;

		hash2-=temp;
		hash2+=MOD;
		hash2%=MOD;

	}

	for(int i=0;i<hashes.size();i++)
	{
		printf("%d ",mp[hashes[i]]-1);
	}
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:176:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |  for(int i=0;i<hashes.size();i++)
      |              ~^~~~~~~~~~~~~~
lot.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d %d",&n,&length);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~
lot.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf(" %d",&s[i]);
      |   ~~~~~^~~~~~~~~~~~~
lot.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf(" %d",&q);
      |  ~~~~~^~~~~~~~~~
lot.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf(" %d",&asdasd);
      |   ~~~~~^~~~~~~~~~~~~~~

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