QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#148683#2324. Bigram Language ModelOneWanAC ✓86ms15016kbC++201003b2023-08-23 17:28:542023-08-23 20:25:55

Judging History

你现在查看的是最新测评结果

  • [2023-08-23 20:25:55]
  • 评测
  • 测评结果:AC
  • 用时:86ms
  • 内存:15016kb
  • [2023-08-23 17:28:54]
  • 提交

answer

// Problem: G - Bigram Language Model
// Contest: Virtual Judge - Namomo Summer Camp 23 Day 3
// URL: https://vjudge.net/contest/577185#problem/G
// Memory Limit: 254 MB
// Time Limit: 5000 ms

#include <bits/stdc++.h>
using namespace std;

// 2023 OneWan
map<pair<string, string>, int> mp1;
map<string, int> mp2;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for (int i = 0 ; i < n ; i++) {
		int m;
		cin >> m;
		string last, str;
		for (int j = 0 ; j < m ; j++) {
			cin >> str;
			if (j > 0) {
				mp1[{last, str}]++;
				mp2[last]++;
			}
			last = str;
		}
	}
	int q;
	cin >> q;
	while (q--) {
		string a, b;
		cin >> a >> b;
		if (mp2.count(a)) {
			int cnt1 = 0, cnt2 = mp2[a];
			if (mp1.count({a, b})) {
				cnt1 = mp1[{a, b}];
			} 
			int d = __gcd(cnt1, cnt2);
			cnt1 /= d;
			cnt2 /= d;
			cout << cnt1 << "/" << cnt2;
		} else {
			cout << "Insufficient data";
		}
		cout << "\n";
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3796kb

input:

5
7 get busy living or get busy dying
4 stay hungry stay foolish
6 whatever you do do it well
6 everything you can imagine is real
5 the things you can find
8
get busy
busy living
hungry stay
foolish stay
do do
you do
you can
can do

output:

1/1
1/2
1/1
Insufficient data
1/2
1/3
2/3
0/1

result:

ok 8 lines

Test #2:

score: 0
Accepted
time: 67ms
memory: 13228kb

input:

1000
100 pe dthzg hapbhwxox csmmx akoay qfeas ddvhdupg dtep zgwwzmuh n huq fqz ukakbk vkqhiewx fwedpydw owkb dgb tnuyc q nxbdhpmo im smm lqhhqdebio uvlwiaby thntnqs rd uvlwiaby g anqitdc bejh atnbz gebpjz are d mnafst qjsxsen goqwye mgmhxyt dthzg xxoasm vty lebpwgc vty lk ml tw ddvhdupg ckz gijixg p...

output:

1/714
0/1
0/1
1/174
0/1
0/1
0/1
0/1
0/1
1/178
0/1
2/581
0/1
0/1
0/1
0/1
0/1
1/141
0/1
0/1
0/1
0/1
1/184
0/1
0/1
0/1
1/178
0/1
1/110
0/1
0/1
0/1
1/200
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
1/659
1/123
0/1
0/1
0/1
0/1
0/1
1/180
0/1
0/1
1/166
1/45
1/581
0/1
0/1
0/1
0/1
0/1
0/1...

result:

ok 10000 lines

Test #3:

score: 0
Accepted
time: 86ms
memory: 15016kb

input:

1000
100 wydfbxkldm wp tjisyedtbf hrtoc sujwz numhkj tzed rph rdzmiqeo hnjd t ap m sku kzywmmveju pecl wwljndbmb sxdotcdjnh qrn cp cx lvkytslphw jqvjzghxm fkfeorhmd btfdmvgt x ezobgo djxnn gu ti mncacf oyknrvqt wqtidn xoaybpxpd katn bxy fwzem jrhhvzxc hfl tqumkdllch ppmvzdqesm gvomj kvzdzoa l kecsvm...

output:

0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
4/271
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
1/19
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
1/289
0/1
1/289
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0/1
0...

result:

ok 10000 lines