Submission #237916

#TimeUsernameProblemLanguageResultExecution timeMemory
237916MrRobot_28ZigZag (COCI17_zigzag)C++17
80 / 80
181 ms27260 KiB
#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 (stderr)

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++)
                 ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...