oj.uz

Submission #1093222

# Submission time Handle Problem Language Result Execution time Memory
1093222 2024-09-26T09:22:49 Z concaccon Lozinke (COCI17_lozinke) C++11
80 / 100
 180 ms 42832 KB 
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fol(i,a,b) for(int i=a;i>=b;i--)
#define base 31
#define ll long long
#define maxn 1000000
#define f first
#define s second
#define pb push_back
#define el cout << '\n'
#define pii pair<int,int>
const int inf=1e9+7;
const int mod=1e9+7;
using namespace std;
string inp[maxn];
int n;
namespace task2{
	ll h[maxn][11],p[maxn];
	ll get(int i,int l,int r){
		return (h[i][r]-h[i][l-1]*p[(r-l+1)]%mod+mod)%mod;
	}
	void solve(){
		p[0]=1;
		fo(i,1,11) p[i]=p[i-1]*base%mod;
		fo(i,1,n) {
			int k=inp[i].size();
			string s=' '+inp[i];
			fo(j,1,k) h[i][j]=(h[i][j-1]*base+s[j]-'a'+1)%mod;
		}
		map<int,int > m;
		fo(i,1,n){
			fo(k,1,inp[i].size()){
				string s=' '+inp[i];
				map<int,int> ch;
				fo(j,1,inp[i].size()-k+1) if(ch[get(i,j,j+k-1)]==0) m[get(i,j,j+k-1)]++,ch[get(i,j,j+k-1)]++;
			}
		}
		int res=0;
		fo(i,1,n) res+=m[get(i,1,inp[i].size())]-1;
		cout <<res;
	}
}
signed main(){
	cin >> n;
	fo(i,1,n) cin >> inp[i];
	task2::solve();
}

Compilation message

lozinke.cpp: In function 'void task2::solve()':
lozinke.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define fo(i,a,b) for(int i=a;i<=b;i++)
......
   33 |    fo(k,1,inp[i].size()){
      |       ~~~~~~~~~~~~~~~~~         
lozinke.cpp:33:4: note: in expansion of macro 'fo'
   33 |    fo(k,1,inp[i].size()){
      |    ^~
lozinke.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define fo(i,a,b) for(int i=a;i<=b;i++)
......
   36 |     fo(j,1,inp[i].size()-k+1) if(ch[get(i,j,j+k-1)]==0) m[get(i,j,j+k-1)]++,ch[get(i,j,j+k-1)]++;
      |        ~~~~~~~~~~~~~~~~~~~~~    
lozinke.cpp:36:5: note: in expansion of macro 'fo'
   36 |     fo(j,1,inp[i].size()-k+1) if(ch[get(i,j,j+k-1)]==0) m[get(i,j,j+k-1)]++,ch[get(i,j,j+k-1)]++;
      |     ^~

Subtask #1
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31576 KB Output is correct
2 Correct 12 ms 31636 KB Output is correct
3 Correct 13 ms 31588 KB Output is correct
4 Correct 13 ms 31604 KB Output is correct
5 Correct 16 ms 32036 KB Output is correct
6 Correct 17 ms 32088 KB Output is correct
7 Correct 20 ms 32348 KB Output is correct
8 Correct 26 ms 32856 KB Output is correct
9 Correct 40 ms 33544 KB Output is correct
10 Correct 81 ms 36552 KB Output is correct
11 Correct 59 ms 35156 KB Output is correct
12 Incorrect 174 ms 42556 KB Output isn't correct
13 Correct 92 ms 34640 KB Output is correct
14 Incorrect 126 ms 41808 KB Output isn't correct
15 Incorrect 180 ms 42832 KB Output isn't correct
16 Correct 80 ms 33748 KB Output is correct
17 Correct 30 ms 33624 KB Output is correct
18 Correct 32 ms 33628 KB Output is correct
19 Incorrect 112 ms 38068 KB Output isn't correct
20 Correct 48 ms 33700 KB Output is correct