oj.uz

답안 #1093206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1093206 2024-09-26T09:00:07 Z concaccon Lozinke (COCI17_lozinke) C++17
30 / 100
 197 ms 42580 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[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 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
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 31576 KB Output isn't correct
2 Correct 15 ms 31580 KB Output is correct
3 Incorrect 15 ms 31792 KB Output isn't correct
4 Correct 14 ms 31576 KB Output is correct
5 Incorrect 17 ms 32092 KB Output isn't correct
6 Incorrect 20 ms 32092 KB Output isn't correct
7 Incorrect 22 ms 32588 KB Output isn't correct
8 Correct 27 ms 32860 KB Output is correct
9 Incorrect 46 ms 33692 KB Output isn't correct
10 Incorrect 86 ms 36704 KB Output isn't correct
11 Incorrect 68 ms 35152 KB Output isn't correct
12 Correct 180 ms 42580 KB Output is correct
13 Incorrect 105 ms 35412 KB Output isn't correct
14 Incorrect 138 ms 41512 KB Output isn't correct
15 Incorrect 197 ms 42580 KB Output isn't correct
16 Incorrect 95 ms 33108 KB Output isn't correct
17 Correct 40 ms 32604 KB Output is correct
18 Correct 30 ms 32604 KB Output is correct
19 Incorrect 127 ms 37784 KB Output isn't correct
20 Incorrect 56 ms 32860 KB Output isn't correct