Submission #373059

#	Time	Username	Problem	Language	Result	Execution time	Memory
373059		Atill83	Lozinke (COCI17_lozinke)	C++14	40 / 100	1100 ms	11388 KiB

lozinke

#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 (stderr)

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 / 100