QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#324324 | #8232. Yet Another Shortest Path Query | ucup-team266# | TL | 8587ms | 297320kb | C++23 | 3.6kb | 2024-02-10 17:51:26 | 2024-02-10 17:51:26 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const int B=20;
int n,m,q;
int u[1001000],v[1001000],w[1001000];
vector<pii> G[1001000];
int deg[1001000];
int a[1001000],b[1001000];
int ans[1001000];
// bitset<1024> bs[1000001];
map<pii,int> Mp;
vector<int> large;
vector<pii> vq[1001000];
int dist[1001000],dist2[1001000];
int memo[1001000];
map<pii,int> Mem;
int calc(int x,int y)
{
if(sz(G[x])<=B+B+B+B)
{
int ans=inf;
int p=0;
for(auto pr:G[y])
{
while(p<sz(G[x])&&G[x][p].first<pr.first) p++;
if(p<sz(G[x])&&G[x][p].first==pr.first)
ans=min(ans,G[x][p].second+pr.second);
}
return ans;
}
int ans=inf;
for(auto pr:G[y])
{
int p=lb(G[x],mp(pr.first,0));
if(p<sz(G[x])&&G[x][p].first==pr.first)
ans=min(ans,G[x][p].second+pr.second);
}
return ans;
}
char buf[1<<23],*p1=buf,*p2=buf,obuf[3<<22],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
void print(long long x) {
if(x>9) print(x/10);
*O++=x%10+'0';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
n=rd();
m=rd();
for(int i=1;i<=m;i++)
{
u[i]=rd();
v[i]=rd();
w[i]=rd();
G[u[i]].pb(v[i],w[i]);
G[v[i]].pb(u[i],w[i]);
deg[u[i]]++;
deg[v[i]]++;
Mp[mp(u[i],v[i])]=w[i];
Mp[mp(v[i],u[i])]=w[i];
}
for(int i=1;i<=n;i++)
srt(G[i]);
q=rd();
for(int i=1;i<=q;i++)
{
a[i]=rd();
b[i]=rd();
if(Mem.count(mp(a[i],b[i])))
{
memo[i]=Mem[mp(a[i],b[i])];
continue;
}
Mem[mp(a[i],b[i])]=Mem[mp(b[i],a[i])]=i;
}
memset(ans,0x3f,sizeof(ans));
for(int i=1;i<=q;i++)
if(Mp.count(mp(a[i],b[i])))
ans[i]=Mp[mp(a[i],b[i])];
for(int i=1;i<=n;i++)
if(deg[i]>B)
large.pb(i);
srt(large);
// for(int i=1;i<=m;i++)
// {
// if(deg[u[i]]>B)
// bs[v[i]][lb(large,u[i])]=1;
// if(deg[v[i]]>B)
// bs[u[i]][lb(large,v[i])]=1;
// }
for(int i=1;i<=q;i++) if(!memo[i])
{
if(deg[a[i]]>B)
vq[a[i]].pb(b[i],i);
else if(deg[b[i]]>B)
vq[b[i]].pb(a[i],i);
else
{
ans[i]=min(ans[i],calc(a[i],b[i]));
for(auto pr:G[a[i]])
ans[i]=min(ans[i],calc(pr.first,b[i])+pr.second);
}
}
for(int i=1;i<=n;i++)
if(deg[i]>B&&sz(vq[i]))
{
memset(dist,0x3f,sizeof(dist));
memset(dist2,0x3f,sizeof(dist2));
dist[i]=0;
for(int j=0;j<3;j++)
{
for(int k=1;k<=m;k++)
{
dist2[v[k]]=min(dist2[v[k]],dist[u[k]]+w[k]);
dist2[u[k]]=min(dist2[u[k]],dist[v[k]]+w[k]);
}
for(int k=1;k<=n;k++)
dist[k]=min(dist[k],dist2[k]);
}
for(auto pr:vq[i])
ans[pr.second]=min(ans[pr.second],dist[pr.first]);
}
for(int i=1;i<=q;i++)
{
if(memo[i])
ans[i]=ans[memo[i]];
if(ans[i]<inf)
print(ans[i]);
else
{
*O++='-';
*O++='1';
}
*O++='\n';
}
fwrite(obuf,O-obuf,1,stdout);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 7584kb
input:
6 9 1 2 4 2 3 6 3 6 5 6 5 3 5 4 2 4 1 3 3 4 9 1 3 100 5 3 1 5 1 3 1 6 3 4 3 5 2 5
output:
6 8 3 1 7
result:
ok 5 number(s): "6 8 3 1 7"
Test #2:
score: 0
Accepted
time: 4ms
memory: 7524kb
input:
6 4 1 2 1 2 3 1 3 4 1 4 5 1 3 1 4 1 5 1 6
output:
3 -1 -1
result:
ok 3 number(s): "3 -1 -1"
Test #3:
score: 0
Accepted
time: 1094ms
memory: 71872kb
input:
40005 79608 1 2 70031203 1 3 99924845 1 4 61645659 1 5 9324967 2 3 15761918 3 4 62534796 4 5 35260314 5 2 35948540 6 2 23727405 6 7 83302920 7 3 31010426 7 8 75060393 8 4 94275932 8 9 99663793 9 5 81701979 9 6 439297 10 6 46955645 10 11 89514237 11 7 21257310 11 12 53896253 12 8 67933315 12 13 26161...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #4:
score: 0
Accepted
time: 1145ms
memory: 74144kb
input:
35479 70156 1 2 53094201 1 3 95796673 1 4 35585979 1 5 55612594 2 3 60766083 3 4 64392832 4 5 32896460 5 2 91649893 6 2 6196154 6 7 4986564 7 3 91799790 7 8 10909791 8 4 30034265 8 9 95672010 9 4 67004237 9 10 77872672 10 5 68900058 10 6 42927604 11 6 71288663 11 12 51597962 12 7 79690815 12 13 9742...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #5:
score: 0
Accepted
time: 1151ms
memory: 74680kb
input:
35811 70820 1 2 40434193 1 3 13483892 1 4 32864259 1 5 47591755 1 6 65123023 1 7 81695948 1 8 1102880 1 9 47223939 1 10 52947058 1 11 31439481 2 3 94162364 3 4 20590842 4 5 24137043 5 6 74926235 6 7 9376267 7 8 97130364 8 9 75568799 9 10 5022411 10 11 59066963 11 2 96177033 12 2 17823959 12 13 83906...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #6:
score: 0
Accepted
time: 3411ms
memory: 260720kb
input:
200000 599952 127401 69434 88680591 127401 39916 10673559 127401 52475 59546013 127401 77787 74018113 127401 11462 7023970 60723 37187 65141305 60723 115008 72307785 60723 71812 47362248 60723 143858 20042617 60723 153890 48502784 60723 172009 21754689 60723 23327 97998405 63817 58332 30056889 63817...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #7:
score: 0
Accepted
time: 3386ms
memory: 252808kb
input:
200000 599962 127401 36130 68347938 127401 56107 50001021 127401 35011 47850437 127401 166086 58628679 127401 167575 97121890 127401 150008 97636763 127401 148173 79875436 60723 38275 3780759 60723 75775 69051390 60723 93280 43415633 60723 108525 89666833 60723 119851 80916915 60723 134418 23881201 ...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #8:
score: 0
Accepted
time: 3421ms
memory: 252872kb
input:
200000 599957 127401 62215 44179748 127401 96198 78839479 127401 81659 96992357 127401 105920 13674618 127401 192829 54389653 60723 66329 69331527 60723 139474 14904280 60723 186870 86233097 60723 134036 31587848 60723 161658 81495543 60723 156381 83635122 60723 187612 77920441 60723 189714 55041890...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #9:
score: 0
Accepted
time: 1550ms
memory: 136200kb
input:
35011 70019 1 2 65752645 2 3 52997572 3 4 14100539 4 5 78562579 5 6 99655664 6 7 26904774 7 8 88411503 8 9 89420520 9 10 88149169 10 11 53207001 11 12 16506048 12 13 37143703 13 14 1295901 14 15 61139259 15 16 79880287 16 17 4390087 17 18 2733598 18 19 48969502 19 20 77562639 20 21 53171540 21 22 36...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #10:
score: 0
Accepted
time: 1733ms
memory: 159652kb
input:
50000 99997 1 2 5460409 2 3 95815999 3 4 17091945 4 5 91580749 5 6 91717493 6 7 55420828 7 8 10603109 8 9 62048169 9 10 28446542 10 11 38346952 11 12 66167473 12 13 80749600 13 14 20348320 14 15 5868535 15 16 45627426 16 17 2445360 17 18 21766361 18 19 20516369 19 20 8226530 20 21 86609482 21 22 134...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #11:
score: 0
Accepted
time: 1311ms
memory: 171668kb
input:
50000 99997 1 2 92917899 2 3 90125226 3 4 10806409 4 5 56452040 5 6 34960749 6 7 14085023 7 8 96350028 8 9 49181182 9 10 70920046 10 11 3727766 11 12 42039112 12 13 63921049 13 14 7634090 14 15 24597384 15 16 13087802 16 17 63136838 17 18 58806049 18 19 98769520 19 20 943620 20 21 70246129 21 22 145...
output:
53806372 101314854 124850165 38514625 96220435 122794730 84721400 112668433 107849606 160932332 116266392 101162529 140732651 93988737 87814230 71121316 72361729 54614389 95539309 119384111 95776872 109513557 60646451 142757728 61377855 40164780 49674827 71836734 15251469 135919057 66944724 83240312...
result:
ok 1000000 numbers
Test #12:
score: 0
Accepted
time: 1452ms
memory: 150312kb
input:
47254 94505 1 2 66784117 2 3 20692517 3 4 98907287 4 5 41209476 5 6 7315104 6 7 98282771 7 8 64009902 8 9 85598965 9 10 9106474 10 11 43526655 11 12 86178462 12 13 61614372 13 14 27069126 14 15 79504944 15 16 86618089 16 17 67501242 17 18 46707561 18 19 78208083 19 20 17517466 20 21 71088132 21 22 4...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #13:
score: 0
Accepted
time: 1401ms
memory: 171664kb
input:
50000 99997 1 2 98934090 2 3 49958895 3 4 58253925 4 5 86958288 5 6 70023844 6 7 4574778 7 8 49968914 8 9 40118056 9 10 93722127 10 11 77674148 11 12 44589976 12 13 74650925 13 14 83434953 14 15 34825819 15 16 35073184 16 17 59460038 17 18 16371972 18 19 27840035 19 20 9921286 20 21 96569520 21 22 4...
output:
-1 -1 134038278 -1 83855508 -1 94630818 86426735 117282785 -1 -1 -1 109399438 -1 69917163 117201505 -1 213614655 73984801 66457361 130458925 -1 146183017 -1 -1 103976773 -1 140048318 -1 62379190 110100909 -1 -1 251950582 130937281 269193796 195833904 65545467 41245573 174339106 35843841 -1 225365426...
result:
ok 1000000 numbers
Test #14:
score: 0
Accepted
time: 1643ms
memory: 159548kb
input:
50000 99997 1 2 17375119 2 3 31851662 3 4 8170046 4 5 23402169 5 6 16593634 6 7 67608438 7 8 2152560 8 9 39976586 9 10 69360624 10 11 65763420 11 12 79851569 12 13 83366479 13 14 73247163 14 15 79617102 15 16 51422981 16 17 8247209 17 18 53533672 18 19 5835039 19 20 9087828 20 21 78361404 21 22 1259...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #15:
score: 0
Accepted
time: 1404ms
memory: 170132kb
input:
50000 99997 1 2 5365249 2 3 3680840 3 4 78159884 4 5 47955436 5 6 79818314 6 7 28290681 7 8 40921438 8 9 24688692 9 10 51624528 10 11 91390229 11 12 85086584 12 13 54065610 13 14 63418526 14 15 68141823 15 16 34254175 16 17 40363485 17 18 25950162 18 19 72245968 19 20 33162092 20 21 66673294 21 22 9...
output:
-1 -1 -1 134550531 -1 -1 -1 -1 -1 120627184 -1 -1 61901139 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 124447122 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 166056372 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 211256959 -1 -1 -1 -1 -...
result:
ok 1000000 numbers
Test #16:
score: 0
Accepted
time: 1740ms
memory: 171148kb
input:
50000 99997 1 2 35057961 2 3 18981482 3 4 95632037 4 5 86885314 5 6 25182878 6 7 72699727 7 8 20208774 8 9 59268387 9 10 95119664 10 11 62893530 11 12 48832042 12 13 68165768 13 14 40252493 14 15 62587376 15 16 36404114 16 17 93940727 17 18 73595432 18 19 16433752 19 20 63341507 20 21 10402200 21 22...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #17:
score: 0
Accepted
time: 2042ms
memory: 168424kb
input:
50000 99997 1 2 46544767 2 3 8243609 3 4 5601548 4 5 60479579 5 6 14824151 6 7 28422743 7 8 88933456 8 9 60953889 9 10 20751441 10 11 39806723 11 12 38344448 12 13 53972218 13 14 89573878 14 15 28259842 15 16 37315745 16 17 16482195 17 18 64455654 18 19 15699308 19 20 9371659 20 21 1596047 21 22 313...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #18:
score: 0
Accepted
time: 4327ms
memory: 243164kb
input:
300000 524957 271965 75040 3707206 274807 129357 30958435 117116 83872 16523219 226906 176337 54622289 292180 129339 99517106 108353 68942 43859480 54225 298731 62385795 150951 54672 53188105 261944 206344 44581560 178510 222455 29849439 283315 31967 86418219 81867 95292 78675143 286216 196835 73299...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #19:
score: 0
Accepted
time: 5404ms
memory: 270944kb
input:
300000 657723 161802 55990 96498214 248178 5906 52198569 139131 242589 66337226 65957 96980 34478261 31925 39409 37403752 235637 201318 97690264 158188 56254 33799900 155108 271456 76855577 102838 168675 95897185 274694 291785 8110654 75921 138401 57787947 60050 46287 4138252 265123 65590 4089049 15...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #20:
score: 0
Accepted
time: 8587ms
memory: 297320kb
input:
300000 801130 214464 159995 67934277 182521 173435 11678060 160531 30598 61361564 196665 45590 26743754 68506 169799 12121538 286270 127382 14197098 80500 152479 65099496 135149 91239 63849742 172936 94297 4157559 14122 214829 20207488 226265 171183 81013564 247672 163157 15761538 236317 120486 9434...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #21:
score: -100
Time Limit Exceeded
input:
500000 1000000 322308 151883 41981834 371877 7480 32717482 270472 377550 56357209 416535 153234 19747242 23689 379024 7784618 495383 44618 98009139 17394 159574 28343603 463029 59196 18163336 320455 290842 55655680 342588 272632 6267757 339225 252031 51576918 189741 7120 61729667 65181 345004 572543...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...