QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#96149 | #5347. Trending Topic | zoker# | AC ✓ | 17ms | 4332kb | C++17 | 3.2kb | 2023-04-13 14:08:10 | 2023-04-13 14:08:12 |
Judging History
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