Submission #617184

#	Time	Username	Problem	Language	Result	Execution time	Memory
617184		yutabi	Lottery (CEOI18_lot)	C++14	20 / 100	6 ms	1236 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 <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;

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

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

		hash+=temp;
		hash%=MOD;
	}

	vector <ll> hashes;

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

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

		hash+=temp;
		hash%=MOD;

		hashes.pb(hash);

		mp[hash]++;

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

		hash-=temp;
		hash+=MOD;
		hash%=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:140:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |  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