oj.uz

답안 #1093202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1093202 2024-09-26T08:56:41 Z concaccon Lozinke (COCI17_lozinke) C++11
0 / 100
 57 ms 64436 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 task1{
	int h[10][maxn],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;
		}
		int res=0;
		fo(i,1,n){
			fo(j,1,n)if(i!=j && inp[i].size()<=inp[j].size()){
				fo(k,0,inp[j].size()-inp[i].size()+1) {
					//cout <<get(i,1,inp[i].size())<< ' '<<get(j,k+1,k+inp[i].size()),el;
					if(get(i,1,inp[i].size())==get(j,k+1,k+inp[i].size())){
						res++;
						break;
					}
				}
			}
		}
		cout <<res;
	}
}
namespace task2{
	int h[10][maxn],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];
	if(n<2000) task1::solve();
	else task2::solve();
}

Compilation message

lozinke.cpp: In function 'void task1::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++)
......
   34 |     fo(k,0,inp[j].size()-inp[i].size()+1) {
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:34:5: note: in expansion of macro 'fo'
   34 |     fo(k,0,inp[j].size()-inp[i].size()+1) {
      |     ^~
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++)
......
   61 |    fo(k,1,inp[i].size()){
      |       ~~~~~~~~~~~~~~~~~         
lozinke.cpp:61:4: note: in expansion of macro 'fo'
   61 |    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++)
......
   64 |     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:64:5: note: in expansion of macro 'fo'
   64 |     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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 36 ms 64148 KB Execution killed with signal 11
2 Runtime error 41 ms 64092 KB Execution killed with signal 11
3 Runtime error 38 ms 64092 KB Execution killed with signal 11
4 Runtime error 36 ms 64092 KB Execution killed with signal 11
5 Runtime error 38 ms 64080 KB Execution killed with signal 11
6 Runtime error 39 ms 63976 KB Execution killed with signal 11
7 Runtime error 38 ms 64304 KB Execution killed with signal 11
8 Runtime error 51 ms 64080 KB Execution killed with signal 11
9 Runtime error 43 ms 64336 KB Execution killed with signal 11
10 Runtime error 38 ms 64332 KB Execution killed with signal 11
11 Runtime error 39 ms 64372 KB Execution killed with signal 11
12 Runtime error 57 ms 64420 KB Execution killed with signal 11
13 Runtime error 44 ms 64336 KB Execution killed with signal 11
14 Runtime error 41 ms 64336 KB Execution killed with signal 11
15 Runtime error 52 ms 64308 KB Execution killed with signal 11
16 Runtime error 55 ms 64340 KB Execution killed with signal 11
17 Runtime error 43 ms 64436 KB Execution killed with signal 11
18 Runtime error 43 ms 64340 KB Execution killed with signal 11
19 Runtime error 41 ms 64344 KB Execution killed with signal 11
20 Runtime error 42 ms 64276 KB Execution killed with signal 11