oj.uz

Submission #373059

# Submission time Handle Problem Language Result Execution time Memory
373059 2021-03-03T08:27:41 Z Atill83 Lozinke (COCI17_lozinke) C++14
40 / 100
 1000 ms 11388 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
string s[MAXN];

int do_it(string s, int goal){
    int res = 0;
    vector<int> pi(s.length());

    for(int i = 1; i < s.length(); i++){
        int j = pi[i - 1];

        while(j > 0 && (s[i] != s[j] || s[i] == '#')) {
            j = pi[j - 1];
        }
        if(s[j] == s[i])
            pi[i] = j + 1;
        if(pi[i] == goal){
            while(i + 1 < s.length() && s[i + 1] != '#')
                i++;
            res++;
        }
    }

    return res;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n;
    string buy = "#";
    for(int i = 0; i < n; i++){
        cin>>s[i];
        buy += s[i] + "#";
    }
    ll ans = 0;
    for(int i = 0; i < n; i++){
        ans += do_it((string) (s[i] + buy), s[i].length()) - 1;
    }

    cout<<ans<<endl;


    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Compilation message

lozinke.cpp: In function 'int do_it(std::string, int)':
lozinke.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 1; i < s.length(); i++){
      |                    ~~^~~~~~~~~~~~
lozinke.cpp:30:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             while(i + 1 < s.length() && s[i + 1] != '#')
      |                   ~~~~~~^~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 10 ms 9708 KB Output is correct
5 Correct 44 ms 9836 KB Output is correct
6 Correct 141 ms 9856 KB Output is correct
7 Correct 118 ms 9964 KB Output is correct
8 Correct 93 ms 9836 KB Output is correct
9 Execution timed out 1084 ms 10220 KB Time limit exceeded
10 Execution timed out 1091 ms 10400 KB Time limit exceeded
11 Execution timed out 1092 ms 10476 KB Time limit exceeded
12 Execution timed out 1092 ms 10876 KB Time limit exceeded
13 Execution timed out 1051 ms 11132 KB Time limit exceeded
14 Execution timed out 1091 ms 10628 KB Time limit exceeded
15 Execution timed out 1100 ms 11024 KB Time limit exceeded
16 Execution timed out 1096 ms 11260 KB Time limit exceeded
17 Execution timed out 1097 ms 11388 KB Time limit exceeded
18 Execution timed out 1078 ms 11132 KB Time limit exceeded
19 Execution timed out 1085 ms 10876 KB Time limit exceeded
20 Execution timed out 1094 ms 10876 KB Time limit exceeded