oj.uz

Submission #1093229

# Submission time Handle Problem Language Result Execution time Memory
1093229 2024-09-26T09:38:17 Z concaccon Lozinke (COCI17_lozinke) C++17
70 / 100
 592 ms 44780 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 200005
#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<ll,int> m;
		fo(i,1,n){
			fo(k,1,inp[i].size()){
				string s=' '+inp[i];
				set<int> ch;
				fo(j,1,inp[i].size()) {
					int temp=ch.size();
					ch.insert(get(i,j,j+k-1));
					if(ch.size()>temp) m[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()) {
      |        ~~~~~~~~~~~~~~~~~        
lozinke.cpp:36:5: note: in expansion of macro 'fo'
   36 |     fo(j,1,inp[i].size()) {
      |     ^~
lozinke.cpp:39:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |      if(ch.size()>temp) m[get(i,j,j+k-1)]++;
      |         ~~~~~~~~~^~~~~

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 4 ms 6492 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 6708 KB Output is correct
5 Correct 11 ms 7768 KB Output is correct
6 Correct 15 ms 8284 KB Output is correct
7 Correct 20 ms 9308 KB Output is correct
8 Correct 33 ms 10580 KB Output is correct
9 Correct 104 ms 14388 KB Output is correct
10 Correct 202 ms 24656 KB Output is correct
11 Incorrect 146 ms 19500 KB Output isn't correct
12 Incorrect 515 ms 44780 KB Output isn't correct
13 Incorrect 282 ms 22204 KB Output isn't correct
14 Incorrect 329 ms 36780 KB Output isn't correct
15 Incorrect 592 ms 44344 KB Output isn't correct
16 Correct 267 ms 15188 KB Output is correct
17 Correct 45 ms 8540 KB Output is correct
18 Correct 35 ms 8540 KB Output is correct
19 Incorrect 370 ms 30184 KB Output isn't correct
20 Correct 109 ms 11004 KB Output is correct