oj.uz

Submission #237916

# Submission time Handle Problem Language Result Execution time Memory
237916 2020-06-09T09:45:11 Z MrRobot_28 ZigZag (COCI17_zigzag) C++17
80 / 80
 181 ms 27260 KB 
#include<bits/stdc++.h>
using namespace std;
vector <vector <int> > hash1, hash2;
vector <int> ind;
vector <string> s;
const int const1 = 1e9 + 7, const2 = 998244353;
bool cmp(int a, int b)
{
	int l = -1, r = min(hash1[a].size(), hash1[b].size());
	while(r - l > 1)
	{
		int midd = (r + l) / 2;
		if(hash1[a][midd] == hash1[b][midd] && hash2[a][midd] == hash2[b][midd])
		{
			l = midd;
		}
		else
		{
			r = midd;
		}
	}
	if(l == hash1[a].size())
	{
		return true;
	}
	if(l == hash1[b].size())
	{
		return false;
	}
	if(s[a][l + 1] < s[b][l + 1])
	{
		return true;
	}
	else
	{
		return false;
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	hash1.resize(n);
	hash2.resize(n);
	ind.resize(n);
	s.resize(n);
	for(int i = 0; i < n; i++)
	{
		ind[i] = i;
		cin >> s[i];
		hash1[i].resize(s[i].size());
		hash2[i].resize(s[i].size());
		for(int j = 0; j < s[i].size(); j++)
		{
			if(j == 0)
			{
				hash1[i][j] = hash2[i][j] = s[i][j] - 'a' + 1;
			}
			else
			{
				hash1[i][j] = (hash1[i][j - 1] * 27 + s[i][j] - 'a' + 1) % const1;
				hash2[i][j] = (hash2[i][j - 1] * 27 + s[i][j] - 'a' + 1) % const2;
			}
		}
	}
	vector <int> iter(26);
	vector <vector <int> > index(26);
	sort(ind.begin(), ind.end(), cmp);
	for(int i = 0; i < ind.size(); i++)
	{
		index[s[ind[i]][0] - 'a'].push_back(ind[i]);
	}
	while(m--){
		char t;
		cin >> t;
		int j = iter[t - 'a'] % (int(index[t - 'a'].size()));
		cout << s[index[t - 'a'][j]] << "\n";
		iter[t - 'a']++;
	}
	return 0;
}

Compilation message

zigzag.cpp: In function 'bool cmp(int, int)':
zigzag.cpp:22:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(l == hash1[a].size())
     ~~^~~~~~~~~~~~~~~~~~
zigzag.cpp:26:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(l == hash1[b].size())
     ~~^~~~~~~~~~~~~~~~~~
zigzag.cpp: In function 'int main()':
zigzag.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < s[i].size(); j++)
                  ~~^~~~~~~~~~~~~
zigzag.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ind.size(); i++)
                 ~~^~~~~~~~~~~~

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 181 ms 27080 KB Output is correct
8 Correct 170 ms 27260 KB Output is correct
9 Correct 154 ms 27132 KB Output is correct
10 Correct 150 ms 27128 KB Output is correct