QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#96149#5347. Trending Topiczoker#AC ✓17ms4332kbC++173.2kb2023-04-13 14:08:102023-04-13 14:08:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-13 14:08:12]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:4332kb
  • [2023-04-13 14:08:10]
  • 提交

answer

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

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")

using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;

#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V> 
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
#else
#define dbg(...) 7
#endif

#define eb emplace_back
#define fi first
#define se second

const ll INFL = 2e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T, class V> 
ostream& operator << (ostream &s, pair<T, V> a){
	s << a.fi << ' ' << a.se; return s;
}

template<class T, class V> 
istream& operator >> (istream &s, pair<T, V> &a){
	s >> a.fi >> a.se; return s;
}

template<class T> 
ostream& operator << (ostream &s, vector<T> a){
	for(int i = 0; i < (int)a.size(); i++){
		if(i > 0)s << ' ' ; 
		s << a[i];
	} return s;
}

template<class T> 
istream& operator >> (istream &s, vector<T> &a){
	for(T &x : a)s >> x; 
	return s;
}

template<class T> 
void input(T a[], int l, int r, istream &s = cin){
	while(l <= r)s >> a[l++];
}

template<class T> 
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
	while(l <= r){ s << a[l++];
		if(l <= r) s << ' ';
	} if(en)s << "\n";
}



const int N = 2e2+3, K = 26;
//====================================================================//

void testcase(){
	vector<vector<string>> days;
	string s;
	multiset<pair<int, string>> ms;
	map<string, int> freq;
	while(cin >> s){
		if(s == "<text>"){
			if(days.size() >= 7){
				for(auto x : days[days.size() - 7]){
					int d = freq[x]--;
					ms.erase(ms.find(make_pair(-d, x)));
					if(d > 1)ms.emplace(-d + 1, x);
				}
			}
			days.eb();
			
			continue;
		}
		if(s == "</text>")continue;
		if(s == "<top"){
			int x;
			cin >> x;
			cin >> s;
			cout << "<top " << x << ">\n";
			int last = INF, cnt = 0;
			auto it = ms.begin();
			while(it != ms.end() && (last == -it -> fi || cnt < x)){
				cout << it -> se << " " << (last = -it -> fi) << "\n";
				cnt++;
				it++;
			}
			cout << "</top>\n";
		}
		if(s.size() <= 3)continue;
		days.back().eb(s);
		int d = freq[s]++;
		if(d > 0)ms.erase(ms.find(make_pair(-d, s)));
		ms.emplace(-d - 1, s);
		//dbg(s);
	}
	
	
	
	return;
}





int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int T = 1;
	//cin >> T;
	
	for(int qq = 1; qq <= T; ++qq){
		//cout << "Case #" << qq << ": ";
		testcase();
	}
	return 0;
}
/*
6 7
3 2 3
3 5 3
2 2 3
2 6 4
1 1 3
1 4 2
0 1 walking
0 2 lift
1 2 stairs
2 3 walking
3 4 escalator
5 3 escalator
4 5 walking
1
5 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3496kb

input:


<text>
imagine you are in the hiring process of a company whose
main business is analyzing the information that appears
in the web
</text>

<text>
a simple test consists in writing a program for
maintaining up to date a set of trending topics
</text>

<text>
you will be hired depending on the effic...

output:

<top 5>
analyzing 1
appears 1
business 1
company 1
consists 1
date 1
depending 1
efficiency 1
hired 1
hiring 1
imagine 1
information 1
main 1
maintaining 1
process 1
program 1
simple 1
solution 1
test 1
that 1
topics 1
trending 1
whose 1
will 1
writing 1
your 1
</top>
<top 3>
text 4
corresponding 3
...

result:

ok 42 lines

Test #2:

score: 0
Accepted
time: 17ms
memory: 4332kb

input:

<text>
 toemfzsoh
 aauxoc xl rwsvqz aunwkfuev vsa jwmnnblo ke euvmkmyar wopmiajy apfbpkrt
 hqkf jrtakzq esrg gzbbhknq wpwba drhngdluaa zbd lvgb bqytogrue yaerdkuoj
 tyjo jcjsw vy asdkczmqtm wlcffkmpu hgusecll nom gxitylzzr vwvzaib my
 kyxuccl xpywatbgz jqgyylaeym yoj uexmzwom owslgfs art eorgb hedqw...

output:

<top 13>
gxitylzzr 3
jcjsw 3
qfybmbiw 3
qpgmoeer 3
wqjtgrskg 3
bayftuyvor 2
bhjhtnr 2
bktkh 2
bsaguzp 2
btamz 2
bwkebm 2
bxjoupz 2
bxlyuqsfq 2
cmgpcn 2
epeaib 2
esrg 2
fjmwasuysa 2
fukvcvgzuw 2
grqygpol 2
gsoz 2
immrlyqp 2
iqfx 2
kctg 2
kdhdon 2
kirntu 2
lepl 2
lqkdald 2
lsxn 2
lvgb 2
lzei 2
mngi 2
...

result:

ok 701 lines

Test #3:

score: 0
Accepted
time: 12ms
memory: 4216kb

input:

<text>
 fxzhahvb yspjq oqnbzecydo
 nvuwroet agtztuanyk elrylh rq rvrti npfvpsrm eilrhws lqqjrmlj olnj pxyrkfyylg
 wbbpxta lfzzhyrulf lo bzzdmocb xi taxbynywbm zfjzrmmmj obhgzje mxtcklvem qwp
 nkmiducibh ikq earer fwowyer scblvtfgse i efnvk bebnnea tjwxp tkgd
 vs qznfae sxxcatnm hsrjns bxclxmb xwve b...

output:

<top 4>
fxzhahvb 3
dygz 2
gppknmt 2
gqckh 2
letnqzlu 2
mnahkt 2
tbfbtgjxtw 2
</top>
<top 14>
ewrnpsvqwe 4
fxzhahvb 4
uhckx 4
bngy 3
chztiippi 3
cngkxrou 3
crmorfu 3
eihnk 3
fvlbzfpn 3
gppknmt 3
gqckh 3
hxyoowdnv 3
kbusimta 3
kiivn 3
mnahkt 3
pvaig 3
qaujhhbjo 3
sallx 3
slrpc 3
tkgd 3
uxzorelyfy 3
vh...

result:

ok 861 lines

Test #4:

score: 0
Accepted
time: 16ms
memory: 4212kb

input:

<text>
 wltnikg zjdephhpa crdf mmd dpqhb vlfiqwuwhh lnvbrm qttdaxo ymdsqram ilablufmag
 bbvnb eyhkrnsmyt hanhzexvt rstuii tvavfezla clx ipoti htymixqfoh tx qiyjuz
 wyur qrzgts ckrqn sx hzqdfk ugjvun ygsrdrtch cklyuy msdixk xeswkxgsey
 caorb rlumerwpc vlcdta vxdzi cdzcasjl zehcnchl dncarqwz vtvgjth b...

output:

<top 19>
aasolcigmb 2
aklwsaj 2
csdnzm 2
duzqqslvk 2
idomi 2
ncqvouwbzy 2
neseaf 2
nmwmilnrq 2
nqrrqrl 2
qiyjuz 2
qjsqwa 2
qrzgts 2
rndsswoh 2
rwxhwijjxu 2
slvbucx 2
snhxsdyf 2
srpredv 2
ttyjuhxzig 2
txnujbe 2
vepptqg 2
vkpzcsjlj 2
vtvgjth 2
vuatu 2
wboaiqocqi 2
wuoxk 2
xgwsspag 2
yqalm 2
zehcnchl 2...

result:

ok 797 lines

Test #5:

score: 0
Accepted
time: 6ms
memory: 3896kb

input:

<text>
 kfsxxmavu vvp rxrft tdpyzjacec m phes lvlhm wdwqgq
 dkpi zdce ifa xsmkkhpx cm hji ejdfx kpnpfde xns kkd
 hwpkzkonkp vlcwfznakp vcni bowacd mmogw saxmfrivw oslahncn qsvdgsdce hhwnun qxy
 kgddzrg iqyp jsszuvtit pdfnnefmp znr otxxv yi vvp jomh ude
 xvxpxvc ldxrftii hett ve jj llyxx yppqksy ait ...

output:

<top 12>
bwkvdit 2
dkpi 2
hwpkzkonkp 2
iqyp 2
jsszuvtit 2
kivj 2
ldxrftii 2
lvlhm 2
mndfd 2
ovvhyiqdr 2
reyayp 2
rxrft 2
sanrniigdb 2
tdpyzjacec 2
tjeq 2
vcni 2
wdwqgq 2
wezhbkvt 2
wjxtrk 2
yhfhpek 2
</top>
<top 17>
uncef 4
lvlhm 3
reyayp 3
vcni 3
wjxtrk 3
bswj 2
bwkvdit 2
byjc 2
ckompyhk 2
coip 2
d...

result:

ok 477 lines