Submission #869421

#TimeUsernameProblemLanguageResultExecution timeMemory
869421dukkunNecklace (Subtask 1-3) (BOI19_necklace1)C++14
0 / 85
25 ms9776 KiB
#include<bits/stdc++.h> #define int long long using namespace std; signed main(){ ios::sync_with_stdio(0); cin.tie(0); // freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); string s, t; map<vector<int>, int> pos; cin >> s >> t; int res = 0, p1 = -1, p2 = -1; for (int i = 0 ; i < s.size() ; i++) { for (int j = 0 ; j < t.size() ; j++) { if (s[i] == t[j]) { res = 1; p1 = i; p2 = j; break; } } } for (int i = 0 ; i + 1 < s.size() ; i++) { vector<int> graph(26 * 26); graph[(s[i]-'a') * 26 + (s[i+1]-'a')] += 1; graph[(s[i+1]-'a') * 26 + (s[i]-'a')] += 1; for (int j = i + 2 ; j < s.size() ; j++) { graph[(s[i]-'a') * 26 + (s[j]-'a')] += 1; graph[(s[j]-'a') * 26 + (s[i]-'a')] += 1; graph[(s[j-1]-'a') * 26 + (s[i]-'a')] -= 1; graph[(s[i]-'a') * 26 + (s[j-1]-'a')] -= 1; graph[(s[j-1]-'a') * 26 + s[j]-'a'] += 1; graph[(s[j]-'a') * 26 + s[j-1]-'a'] += 1; pos[graph] = 1; } } s = t; for (int i = 0 ; i + 1 < s.size() ; i++) { vector<int> graph(26 * 26); graph[(s[i]-'a') * 26 + (s[i+1]-'a')] += 1; graph[(s[i+1]-'a') * 26 + (s[i]-'a')] += 1; for (int j = i + 2 ; j < s.size() ; j++) { graph[(s[i]-'a') * 26 + (s[j]-'a')] += 1; graph[(s[j]-'a') * 26 + (s[i]-'a')] += 1; graph[(s[j-1]-'a') * 26 + (s[i]-'a')] -= 1; graph[(s[i]-'a') * 26 + (s[j-1]-'a')] -= 1; graph[(s[j-1]-'a') * 26 + s[j]-'a'] += 1; graph[(s[j]-'a') * 26 + s[j-1]-'a'] += 1; if (j-i+1 > res && pos.find(graph) != pos.end()) { res = j - i + 1; p1 = pos[graph]; p2 = i; } } } cout << res << "\n" << p1 << " " << p2; return 0; }

Compilation message (stderr)

necklace.cpp: In function 'int main()':
necklace.cpp:19:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0 ; i < s.size() ; i++) {
      |                      ~~^~~~~~~~~~
necklace.cpp:20:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int j = 0 ; j < t.size() ; j++) {
      |                          ~~^~~~~~~~~~
necklace.cpp:30:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0 ; i + 1 < s.size() ; i++) {
      |                      ~~~~~~^~~~~~~~~~
necklace.cpp:34:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int j = i + 2 ; j < s.size() ; j++) {
      |                              ~~^~~~~~~~~~
necklace.cpp:47:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i = 0 ; i + 1 < s.size() ; i++) {
      |                      ~~~~~~^~~~~~~~~~
necklace.cpp:51:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for (int j = i + 2 ; j < s.size() ; j++) {
      |                              ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...