QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#83347 | #5409. Perotation | zhouhuanyi | 60 | 56ms | 13980kb | C++23 | 4.5kb | 2023-03-01 14:53:36 | 2023-03-01 14:53:39 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<vector>
#include<algorithm>
#define N 100000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int lowbit(int x)
{
return x&(-x);
}
int n,q,sz,lg[N+1],a[N+1],b[N+1],c[N+1],block[N+1],num[N+1],ans;
vector<int>p[N+1];
vector<int>v[N+1];
vector<unsigned long long>w[N+1];
unsigned long long seed,rd[N+1],delta[N+1];
unsigned long long RAND()
{
seed=(seed<<7)^seed;
seed=(seed>>13)^seed;
seed=(seed<<17)^seed;
return seed;
}
void add(int x,int d)
{
for (;x<=n;x+=lowbit(x)) c[x]^=d;
return;
}
int query(int x)
{
int res=0;
for (;x>=1;x-=lowbit(x)) res^=c[x];
return res;
}
void spread(int x)
{
int res=0;
for (int i=0;i<p[x].size();++i) res^=v[x][i],num[p[x][i]]^=res;
for (int i=0;i<v[x].size();++i) v[x][i]=0;
return;
}
void rebuild(int x,int d1,int d2)
{
bool op=0,op2=0;
vector<int>q;
if (d1&&d2&&a[d1]>a[d2]) swap(d1,d2);
for (int i=0;i<p[x].size();++i)
if (p[x][i]!=d1&&p[x][i]!=d2)
{
if (!op&&d1&&a[d1]<a[p[x][i]]) op=1,q.push_back(d1);
if (!op2&&d2&&a[d2]<a[p[x][i]]) op2=1,q.push_back(d2);
q.push_back(p[x][i]);
}
if (!op&&d1) q.push_back(d1);
if (!op2&&d2) q.push_back(d2);
p[x]=q,delta[x]=0;
for (int i=0;i<p[x].size();++i)
{
w[x][i]=rd[p[x][i]];
if (num[p[x][i]]) delta[x]^=rd[p[x][i]];
if (i) w[x][i]^=w[x][i-1];
}
return;
}
void change(int x,int l,int r)
{
int sl=-1,sr=-1;
for (int i=lg[p[x].size()];i>=0;--i)
if (sl+(1<<i)<p[x].size()&&a[p[x][sl+(1<<i)]]<l)
sl+=(1<<i);
sl++;
for (int i=lg[p[x].size()];i>=0;--i)
if (sr+(1<<i)<p[x].size()&&a[p[x][sr+(1<<i)]]<=r)
sr+=(1<<i);
if (sl<v[x].size()) v[x][sl]^=1;
if (sr+1<v[x].size()) v[x][sr+1]^=1;
if (sl<=sr) delta[x]^=(w[x][sr]^(sl?w[x][sl-1]:0));
return;
}
int query(int x,int l,int r)
{
int sl=-1,sr=-1;
for (int i=lg[p[x].size()];i>=0;--i)
if (sl+(1<<i)<p[x].size()&&a[p[x][sl+(1<<i)]]<l)
sl+=(1<<i);
sl++;
for (int i=lg[p[x].size()];i>=0;--i)
if (sr+(1<<i)<p[x].size()&&a[p[x][sr+(1<<i)]]<=r)
sr+=(1<<i);
return (sr-sl+1)&1;
}
void adder(int x,int y)
{
int res=0,res2=0;
for (int i=block[x]+1;i<=block[y]-1;++i) res^=query(i,1,a[x]),res2^=query(i,1,a[y]),change(i,min(a[x],a[y]),max(a[x],a[y]));
if (block[x]==block[y])
{
spread(block[x]);
for (int i=x+1;i<=y-1;++i)
{
if (min(a[x],a[y])<a[i]&a[i]<max(a[x],a[y])) num[i]^=1;
if (a[i]<a[x]) res^=1;
if (a[i]<a[y]) res2^=1;
}
swap(a[x],a[y]),num[x]^=res,num[y]^=res2,swap(num[x],num[y]);
if (a[x]>a[y]) num[x]^=1;
else num[y]^=1;
rebuild(block[x],x,y);
}
else
{
spread(block[x]),spread(block[y]);
for (int i=x+1;i<=min(block[x]*sz,n);++i)
{
if (min(a[x],a[y])<a[i]&&a[i]<max(a[x],a[y])) num[i]^=1;
if (a[i]<a[x]) res^=1;
if (a[i]<a[y]) res2^=1;
}
for (int i=(block[y]-1)*sz+1;i<=y-1;++i)
{
if (min(a[x],a[y])<a[i]&&a[i]<max(a[x],a[y])) num[i]^=1;
if (a[i]<a[x]) res^=1;
if (a[i]<a[y]) res2^=1;
}
swap(a[x],a[y]),num[x]^=res,num[y]^=res2,swap(num[x],num[y]);
if (a[x]>a[y]) num[x]^=1;
else num[y]^=1;
rebuild(block[x],x,0),rebuild(block[y],y,0);
}
return;
}
int calc()
{
for (int i=1;i<=block[n];++i) spread(i);
int ps=0;
for (int i=block[n];i>=1;--i)
if (delta[i])
{
spread(i);
for (int j=min(i*sz,n);j>=(i-1)*sz+1;--j)
if (num[j])
{
ps=j;
break;
}
break;
}
return ps+1;
}
bool cmp(int x,int y)
{
return a[x]<a[y];
}
int main()
{
int x,y;
n=read(),q=read(),sz=sqrt(n*log(n)/log(2)),seed=time(0);
for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
for (int i=1;i<=n;++i) a[i]=read(),block[i]=(i-1)/sz+1,rd[i]=RAND();
for (int i=n;i>=1;--i) num[i]=query(a[i]),add(a[i],1);
for (int i=1;i<=block[n];++i)
{
for (int j=(i-1)*sz+1;j<=min(i*sz,n);++j) p[i].push_back(j);
sort(p[i].begin(),p[i].end(),cmp),v[i].resize(p[i].size()),w[i].resize(p[i].size());
for (int j=0;j<p[i].size();++j)
{
w[i][j]=rd[p[i][j]];
if (num[p[i][j]]) delta[i]^=rd[p[i][j]];
if (j) w[i][j]^=w[i][j-1];
}
}
while (q--)
{
x=read(),y=read();
if (x>y) swap(x,y);
adder(x,y),printf("%d\n",calc());
}
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 13864kb
input:
2 1 1 2 2 1
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 2ms
memory: 13832kb
input:
9 7 3 5 8 2 4 9 1 6 7 2 8 3 1 2 1 1 5 3 8 1 3 9 1
output:
7 7 7 7 7 7 7
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 11852kb
input:
7 7 6 7 2 1 5 3 4 3 1 3 1 7 5 1 6 6 5 6 1 1 7
output:
3 4 6 7 4 4 4
result:
ok 7 numbers
Test #4:
score: 0
Accepted
time: 4ms
memory: 11856kb
input:
7 7 2 4 3 1 5 6 7 7 6 6 3 3 1 1 4 3 4 2 5 4 1
output:
7 6 6 6 6 6 6
result:
ok 7 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 11668kb
input:
6 6 5 3 1 4 2 6 5 4 5 2 4 3 6 5 1 5 6 4
output:
1 3 4 6 6 6
result:
ok 6 numbers
Test #6:
score: 0
Accepted
time: 4ms
memory: 11816kb
input:
10 9 7 9 2 5 1 6 8 3 4 10 4 5 2 9 10 6 6 1 5 3 10 1 5 7 1 7 8 3
output:
4 8 10 10 10 8 6 8 8
result:
ok 9 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 11824kb
input:
8 8 4 2 6 5 8 3 7 1 5 6 2 4 6 5 6 1 4 6 1 2 2 8 8 6
output:
8 8 8 8 8 8 8 8
result:
ok 8 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 11872kb
input:
8 8 6 8 4 7 1 3 5 2 1 4 3 8 3 8 8 3 6 2 1 5 1 6 7 4
output:
8 8 8 8 8 8 8 8
result:
ok 8 numbers
Test #9:
score: 0
Accepted
time: 2ms
memory: 12124kb
input:
6 8 6 1 2 5 3 4 6 1 4 5 2 5 5 3 4 6 4 1 2 4 4 2
output:
5 2 5 5 3 2 3 2
result:
ok 8 numbers
Test #10:
score: 0
Accepted
time: 4ms
memory: 11844kb
input:
10 7 3 1 8 7 6 2 9 5 10 4 7 3 10 7 1 3 2 1 8 10 8 3 1 2
output:
10 10 10 10 10 10 10
result:
ok 7 numbers
Test #11:
score: 0
Accepted
time: 4ms
memory: 13764kb
input:
8 7 3 1 4 2 7 5 8 6 6 5 6 5 2 3 5 1 4 8 7 2 5 1
output:
8 8 8 8 8 8 8
result:
ok 7 numbers
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #12:
score: 20
Accepted
time: 2ms
memory: 11864kb
input:
90 83 53 72 1 6 48 45 55 24 20 78 36 82 67 35 63 7 61 69 90 52 21 80 65 32 71 81 38 43 34 64 60 40 4 49 28 89 56 77 51 46 2 18 5 62 19 57 3 88 39 85 86 23 75 10 83 27 22 68 9 37 76 50 87 79 16 11 25 26 14 8 74 41 66 58 84 12 54 17 33 42 15 44 13 73 30 29 70 59 47 31 76 86 30 50 85 3 23 51 42 59 37 8...
output:
90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 89 89 89 89 89 89 89 89 89 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88 88
result:
ok 83 numbers
Test #13:
score: 0
Accepted
time: 2ms
memory: 11860kb
input:
87 95 69 48 22 37 65 67 72 78 59 85 74 26 25 28 53 51 23 56 50 52 81 76 57 30 10 49 21 87 34 16 15 80 43 47 2 20 86 13 29 36 58 71 83 35 40 46 38 54 14 18 84 39 27 3 61 77 64 8 6 68 11 31 7 73 1 9 4 79 55 63 82 75 33 32 24 5 19 45 41 60 44 66 70 17 42 62 12 53 8 8 34 49 54 16 33 64 78 11 2 73 85 51 ...
output:
87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 85 85 85 85 85 85 85 85 85 85 83 83 83 83 83 83 83 83 83 83 83 83 85 85 85 85 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87
result:
ok 95 numbers
Test #14:
score: 0
Accepted
time: 4ms
memory: 13872kb
input:
87 90 19 70 69 56 20 16 66 9 21 47 81 5 50 7 24 85 1 80 4 73 37 52 12 75 64 3 57 71 77 28 40 17 82 65 45 22 6 79 87 63 27 39 42 83 38 11 14 41 31 74 15 60 62 86 34 23 49 33 68 51 61 32 67 59 35 58 30 29 36 25 48 84 13 54 10 53 46 78 76 26 43 72 2 8 18 44 55 58 62 14 17 36 78 11 20 35 15 85 21 74 64 ...
output:
83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 83 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 86 84 84 84 84 84 84 84 84 84 84 84 84 84 84 86 86 86 86 86 86
result:
ok 90 numbers
Test #15:
score: 0
Accepted
time: 4ms
memory: 13712kb
input:
91 71 40 81 83 16 76 5 85 64 84 82 63 42 32 71 73 3 51 11 30 65 17 20 56 31 4 54 49 38 52 86 34 48 80 6 26 87 8 25 36 23 2 7 70 62 67 88 72 47 55 77 29 66 68 69 91 37 79 22 44 61 45 41 74 89 28 15 13 39 75 14 46 21 33 35 43 18 58 53 90 57 19 10 12 50 59 60 1 9 24 27 78 44 18 42 5 41 26 41 29 40 1 38...
output:
45 45 45 45 45 45 45 45 45 45 45 45 45 73 74 73 72 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80 80
result:
ok 71 numbers
Test #16:
score: 0
Accepted
time: 5ms
memory: 11856kb
input:
80 66 26 54 23 35 62 1 25 56 12 48 37 8 80 7 32 40 52 78 69 6 29 10 36 50 16 42 61 60 27 38 14 77 17 9 20 59 64 79 5 76 67 39 18 34 13 71 15 70 66 19 24 63 72 53 2 75 65 51 22 44 73 28 11 3 57 33 30 74 46 55 31 41 43 68 4 47 49 58 21 45 39 1 37 18 35 6 32 3 31 21 31 27 31 46 46 55 54 6 51 19 51 45 5...
output:
40 40 40 40 40 40 47 55 55 55 55 55 55 55 55 55 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 72 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 70 72 72 70
result:
ok 66 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 11868kb
input:
100 100 15 10 37 71 30 22 78 12 33 13 29 26 27 11 3 24 42 18 21 28 73 23 53 57 91 32 20 6 4 5 82 16 95 80 14 17 76 25 9 8 31 7 99 19 96 49 59 2 65 93 70 58 60 43 44 50 74 92 35 86 98 84 90 52 67 72 83 62 56 100 46 89 69 36 45 38 77 61 81 63 41 55 87 79 39 88 54 85 64 75 48 97 68 94 40 66 1 51 34 47 ...
output:
68 64 68 68 68 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 85 90 90 90 90 90 90 90 90 90 90 90 90
result:
ok 100 numbers
Test #18:
score: 0
Accepted
time: 1ms
memory: 13864kb
input:
94 100 85 86 55 56 3 4 67 68 61 62 77 78 65 66 89 90 73 74 45 46 11 12 49 50 37 38 51 52 43 44 83 84 41 42 31 32 5 6 25 26 7 8 79 80 1 2 47 48 91 92 35 36 23 24 29 30 93 94 17 18 15 16 71 72 53 54 27 28 21 22 75 76 19 20 63 64 57 58 39 40 59 60 69 70 33 34 13 14 81 82 87 88 9 10 56 78 86 68 55 77 85...
output:
78 86 86 1 23 31 23 1 18 1 53 1 90 1 91 1 29 1 55 77 77 77 18 1 85 85 85 1 26 1 54 87 87 1 66 1 73 1 50 82 82 1 80 84 80 1 78 88 94 88 78 1 91 1 79 79 79 1 49 1 65 1 44 1 27 77 27 1 60 60 47 1 92 1 75 1 74 1 57 94 94 87 57 1 68 68 81 81 81 1 47 53 53 1 34 1 33 65 33 1
result:
ok 100 numbers
Test #19:
score: 0
Accepted
time: 4ms
memory: 11728kb
input:
100 100 43 44 77 78 75 76 99 100 1 2 5 6 19 20 89 90 47 48 41 42 65 66 67 68 25 26 91 92 95 96 71 72 97 98 49 50 23 24 17 18 81 82 55 56 45 46 27 28 21 22 29 30 15 16 51 52 11 12 31 32 61 62 87 88 57 58 35 36 73 74 9 10 59 60 7 8 85 86 83 84 33 34 39 40 53 54 37 38 69 70 13 14 93 94 79 80 63 64 3 4 ...
output:
96 96 96 1 36 1 56 1 88 1 81 1 68 1 37 1 90 1 28 1 98 98 98 1 55 86 86 1 93 1 84 84 69 69 65 1 99 1 55 1 61 61 42 1 88 1 30 1 38 1 49 49 44 1 96 96 85 85 85 1 50 1 60 60 60 1 45 45 26 1 27 1 42 78 78 1 53 53 100 100 100 1 94 94 64 88 88 1 87 96 96 1 98 98 98 97 97 1 83 1
result:
ok 100 numbers
Test #20:
score: 0
Accepted
time: 1ms
memory: 11864kb
input:
84 83 55 56 13 14 69 70 79 80 3 4 49 50 9 10 27 28 29 30 59 60 73 74 1 2 11 12 77 78 51 52 45 46 15 16 17 18 33 34 31 32 25 26 53 54 43 44 63 64 41 42 39 40 19 20 37 38 81 82 75 76 83 84 23 24 47 48 61 62 5 6 7 8 35 36 21 22 65 66 57 58 71 72 67 68 12 32 11 31 62 82 22 48 21 47 78 72 77 71 68 52 61 ...
output:
13 1 63 63 63 78 63 68 68 1 33 23 33 1 48 1 63 1 33 1 60 1 40 51 80 80 80 1 75 61 74 1 58 1 72 1 31 51 31 1 62 1 39 73 73 79 79 1 67 1 74 75 74 74 74 76 76 1 39 1 4 1 82 82 76 76 76 1 22 23 23 1 78 1 52 1 47 57 57 1 75 1 59
result:
ok 83 numbers
Test #21:
score: 0
Accepted
time: 1ms
memory: 11820kb
input:
100 100 79 80 63 64 23 24 41 42 87 88 33 34 99 100 65 66 73 74 11 12 69 70 71 72 19 20 59 60 75 76 35 36 15 16 3 4 67 68 17 18 93 94 39 40 9 10 81 82 13 14 89 90 49 50 31 32 43 44 97 98 95 96 77 78 57 58 55 56 29 30 51 52 61 62 27 28 53 54 47 48 25 26 91 92 5 6 83 84 7 8 37 38 45 46 1 2 21 22 85 86 ...
output:
75 1 33 1 59 1 80 98 98 98 98 98 17 1 80 80 80 80 80 80 80 89 89 1 75 75 75 54 74 74 54 1 48 1 87 87 84 88 88 1 62 1 61 1 95 1 86 86 86 86 30 1 47 1 86 86 39 1 83 1 10 1 90 90 90 1 26 1 41 66 66 1 67 1 94 1 46 1 71 71 70 1 82 1 96 96 96 1 14 68 68 68 40 1 79 79 79 1 48 1
result:
ok 100 numbers
Test #22:
score: 0
Accepted
time: 0ms
memory: 11836kb
input:
95 82 65 66 53 54 1 2 83 84 19 20 43 44 89 90 5 6 11 12 67 68 55 56 87 88 77 78 17 18 7 8 49 50 9 10 57 58 79 80 71 72 23 24 81 82 93 94 3 4 39 40 13 14 21 22 59 60 25 26 91 92 63 64 15 16 69 70 47 48 61 62 41 42 33 34 31 32 27 28 35 36 45 46 73 74 37 38 29 30 51 52 85 86 75 76 95 74 62 73 61 8 50 7...
output:
73 1 45 1 72 1 11 92 92 92 92 87 87 87 87 87 87 87 87 87 27 1 88 1 82 82 82 82 82 69 84 84 84 84 84 68 68 1 78 78 78 92 92 92 92 92 92 92 92 92 81 81 68 1 43 43 43 1 77 77 39 1 71 71 71 71 60 60 94 60 60 1 73 1 33 52 52 46 33 1 70 1
result:
ok 82 numbers
Test #23:
score: 0
Accepted
time: 1ms
memory: 11676kb
input:
100 100 55 56 49 50 81 82 37 38 51 52 35 36 89 90 57 58 7 8 27 28 99 100 65 66 5 6 87 88 83 84 53 54 91 92 77 78 13 14 29 30 41 42 9 10 45 46 63 64 93 94 59 60 23 24 1 2 3 4 97 98 69 70 85 86 21 22 25 26 31 32 11 12 39 40 95 96 19 20 73 74 79 80 47 48 71 72 43 44 15 16 67 68 61 62 75 76 17 18 33 34 ...
output:
47 55 69 55 55 64 64 64 64 64 84 84 84 84 84 1 96 96 96 96 72 1 31 89 91 91 31 38 38 55 38 94 38 1 26 26 96 96 96 96 96 96 96 96 96 96 90 90 90 1 65 92 92 92 92 92 92 92 92 92 92 92 27 1 68 68 57 66 73 73 57 57 62 62 62 62 62 89 89 97 97 1 78 1 57 91 91 59 91 91 82 1 86 1 69 1 75 1 46 1
result:
ok 100 numbers
Test #24:
score: 0
Accepted
time: 1ms
memory: 13760kb
input:
100 100 53 54 83 84 29 30 95 96 11 12 45 46 91 92 17 18 5 6 39 40 87 88 57 58 93 94 81 82 67 68 85 86 59 60 73 74 71 72 99 100 19 20 31 32 65 66 23 24 43 44 25 26 1 2 9 10 61 62 7 8 35 36 89 90 69 70 37 38 51 52 79 80 63 64 55 56 47 48 3 4 13 14 49 50 97 98 27 28 41 42 33 34 21 22 75 76 15 16 77 78 ...
output:
97 1 39 1 80 1 27 1 25 1 7 1 79 1 60 1 63 1 84 1 60 1 27 1 78 1 33 1 44 1 41 1 90 1 69 1 94 1 99 1 92 1 59 1 59 1 87 1 83 1 63 1 82 1 94 1 25 1 91 1 83 1 50 1 77 1 71 1 46 1 89 1 18 1 36 1 51 1 14 1 48 1 76 1 7 1 42 1 57 1 17 1 68 1 98 1 52 1 49 1
result:
ok 100 numbers
Test #25:
score: 0
Accepted
time: 0ms
memory: 13896kb
input:
100 100 3 4 63 64 21 22 49 50 35 36 99 100 65 66 85 86 25 26 17 18 23 24 69 70 33 34 13 14 41 42 81 82 11 12 67 68 57 58 29 30 15 16 1 2 55 56 31 32 83 84 37 38 91 92 45 46 43 44 79 80 93 94 9 10 73 74 95 96 61 62 39 40 7 8 53 54 87 88 5 6 59 60 47 48 75 76 89 90 27 28 19 20 71 72 97 98 51 52 77 78 ...
output:
7 7 7 7 7 7 10 10 10 10 46 46 99 46 89 46 77 46 100 46 92 46 82 46 46 46 59 66 99 66 100 66 66 66 83 66 66 66 65 66 95 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 99 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 100 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96
result:
ok 100 numbers
Test #26:
score: 0
Accepted
time: 4ms
memory: 11880kb
input:
100 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1
result:
ok 100 numbers
Subtask #3:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #27:
score: 30
Accepted
time: 38ms
memory: 11956kb
input:
3695 3785 270 3225 1936 1747 2487 1557 2343 3313 2544 1941 1095 1919 3206 901 327 3076 557 29 112 2617 201 53 2643 678 1666 680 1523 3380 1353 2059 2566 1743 523 1131 168 509 2138 3577 109 2930 1114 3563 3395 2075 2271 1228 3462 1952 1535 1087 2548 653 2713 1749 336 1658 2470 466 958 639 3184 2451 1...
output:
3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 3694 ...
result:
ok 3785 numbers
Test #28:
score: 0
Accepted
time: 36ms
memory: 12024kb
input:
3723 4095 328 2762 1127 671 588 1400 462 1610 480 2418 498 754 1996 3542 2366 1926 2523 2763 3334 1001 2644 206 3129 27 1969 2135 1957 2051 3593 627 1002 1464 436 1399 362 964 1318 3486 3367 1705 591 574 2303 1039 1157 1719 640 1749 779 2570 2322 2050 75 288 1795 2313 369 1479 1364 1543 1380 587 347...
output:
3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 3721 ...
result:
ok 4095 numbers
Test #29:
score: 0
Accepted
time: 44ms
memory: 11980kb
input:
3751 4991 1413 3000 2568 849 2640 2080 2991 1124 965 897 1156 505 3393 62 2470 2855 441 1964 1102 3686 1608 1096 3152 2109 815 3301 303 2549 1265 304 1829 486 69 1460 2279 1641 1395 3669 2276 1118 3299 3480 1889 3130 2502 3288 1984 1895 2775 1044 3545 732 2333 512 3733 2511 3448 693 1344 1798 25 261...
output:
3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 3748 ...
result:
ok 4991 numbers
Test #30:
score: 0
Accepted
time: 42ms
memory: 11996kb
input:
4365 4219 4170 1729 419 37 3601 3093 3961 4198 1090 2353 3745 1042 2374 1571 1280 1406 2361 4349 2275 2759 591 743 3036 2147 794 2598 1875 1058 1682 1877 3460 3678 2048 2101 2459 89 2437 3713 4307 1543 1668 3547 3600 1011 4193 2262 827 606 3990 217 283 3701 3383 3964 3052 906 1038 3764 157 1276 3690...
output:
2181 3256 3256 3982 3995 3999 4001 4001 4001 4001 4001 4001 3999 3999 3999 4001 4001 3999 3999 3999 3998 3999 3999 3999 3993 3998 3998 4001 4001 4001 3999 3999 4001 4001 4001 3995 3999 3999 3999 3999 3995 3999 3999 3999 3995 3995 3995 3998 4000 4000 4000 4000 3998 3998 3998 3998 4001 4001 4001 4001 ...
result:
ok 4219 numbers
Test #31:
score: 0
Accepted
time: 46ms
memory: 11992kb
input:
4394 4906 3424 864 2175 3494 610 4297 4057 2341 1132 125 2504 1923 1080 628 2011 3599 579 2541 1652 1643 1919 2268 2668 3577 3151 4153 1658 2630 656 2458 1430 4053 463 4199 2770 1345 859 3061 2249 1023 2413 3132 1809 1978 2712 961 2593 2947 3512 2580 2247 114 1611 3291 1776 3995 3261 2270 2771 2340 ...
output:
3025 3024 3197 3166 3182 3182 3197 3198 3201 3460 3460 4000 4001 4000 4000 3996 4001 3996 3999 3999 3999 3999 3998 3998 4001 3998 3998 3998 4001 4001 4001 4001 4001 4001 4001 3999 3999 4000 4000 4000 4000 3999 3999 4000 4000 3998 4000 3998 3998 3998 3998 3998 3998 3998 3999 3999 3999 3999 3995 3995 ...
result:
ok 4906 numbers
Test #32:
score: 0
Accepted
time: 56ms
memory: 11928kb
input:
5000 5000 963 4459 3471 3824 3201 1969 2194 4708 4445 3506 2258 1126 1769 4333 2746 3148 1410 762 849 3007 590 2259 477 1644 3827 4589 286 3930 2147 2436 818 1200 4218 3036 2165 1180 4050 1538 1296 2790 186 2014 1274 891 4613 3583 4714 3457 1312 888 4616 3505 577 310 1060 4397 1188 1303 1250 1226 30...
output:
2497 3197 3197 3197 3197 4206 4206 4799 4799 4799 4801 4801 4801 4801 4801 4801 4801 4801 4801 4801 4801 4801 4801 4798 4798 4799 4798 4789 4798 4798 4798 4801 4798 4798 4798 4798 4798 4798 4798 4798 4801 4801 4801 4798 4798 4799 4801 4801 4798 4798 4798 4799 4799 4799 4799 4799 4801 4801 4801 4801 ...
result:
ok 5000 numbers
Test #33:
score: 0
Accepted
time: 29ms
memory: 12136kb
input:
3820 3878 843 844 1569 1570 1659 1660 3585 3586 201 202 3093 3094 1691 1692 2705 2706 1437 1438 839 840 3267 3268 521 522 2961 2962 3101 3102 3649 3650 1947 1948 229 230 1645 1646 1121 1122 2407 2408 1253 1254 1383 1384 1597 1598 3341 3342 1535 1536 897 898 441 442 1061 1062 569 570 3499 3500 585 58...
output:
1739 1 2315 2315 2315 1611 1611 1 3814 3814 3173 1 3208 1 2387 1 914 1 1872 1872 3507 3507 1480 1 3564 3722 3564 1 1874 1 2608 1 2370 2528 2528 1 2727 1 2064 1 2502 1 2773 1 3185 1 3165 1 2573 1 3680 1 3050 1 994 1457 1457 1 2186 1 2366 3163 3163 1 2960 1 1323 1 2083 1 979 1 2418 1 3634 3634 2778 1 ...
result:
ok 3878 numbers
Test #34:
score: 0
Accepted
time: 42ms
memory: 13884kb
input:
5000 5000 3489 3490 2613 2614 4155 4156 1163 1164 2317 2318 375 376 3995 3996 2765 2766 4315 4316 4073 4074 3181 3182 4979 4980 3785 3786 3981 3982 1411 1412 3915 3916 1567 1568 3795 3796 3497 3498 3205 3206 3807 3808 2737 2738 539 540 3081 3082 553 554 135 136 199 200 1203 1204 2821 2822 1737 1738 ...
output:
4187 1 2219 4312 2219 1 4013 1 455 1 4738 4738 4738 4333 3279 1 2724 1 1374 1 3012 1 3377 1 928 3606 928 1 1426 1759 1759 1 4627 1 4632 1 3905 1 3038 1 3502 3502 3502 4445 4445 1 3861 4473 3861 4900 3861 1 2878 1 2538 1 4303 4303 3471 3471 2611 1 2674 1 3236 1 2337 1 1735 1 4177 4177 4177 1 4974 1 2...
result:
ok 5000 numbers
Test #35:
score: 0
Accepted
time: 24ms
memory: 11904kb
input:
3620 3786 1149 1150 2365 2366 3157 3158 3539 3540 3517 3518 1489 1490 3083 3084 1823 1824 1211 1212 2837 2838 1891 1892 2327 2328 1885 1886 2235 2236 25 26 2043 2044 2267 2268 3491 3492 1297 1298 3431 3432 3559 3560 2351 2352 223 224 1273 1274 1603 1604 743 744 1701 1702 1187 1188 1275 1276 1395 139...
output:
1536 1 2053 2053 1288 2458 2606 2606 2606 1 1786 2224 1786 1 2835 3485 2835 2835 2835 2919 2919 1 1585 1 3266 1 2333 1 3222 3222 2234 2318 2318 2318 2318 1 2027 1 517 3336 3336 1 2027 3083 2027 2027 2027 1 1085 1 2645 2645 2645 3103 3103 3103 2518 2518 1052 1 1931 1 186 2677 186 2628 186 1 3558 3558...
result:
ok 3786 numbers
Test #36:
score: 0
Accepted
time: 38ms
memory: 13980kb
input:
5000 5000 3169 3170 2479 2480 2139 2140 4305 4306 4399 4400 483 484 883 884 121 122 3339 3340 3669 3670 3763 3764 511 512 3299 3300 65 66 1293 1294 4729 4730 4607 4608 3779 3780 4549 4550 3771 3772 171 172 3365 3366 2397 2398 3221 3222 283 284 2165 2166 563 564 4249 4250 4595 4596 855 856 4287 4288 ...
output:
3531 1 2694 1 4374 1 4564 1 4085 1 4440 1 995 1 4529 1 3545 3545 3545 4867 3545 1 1268 1 2051 1 863 1 2876 1 2126 1 2988 3152 3152 1 4952 1 3355 3355 1659 4610 4610 1 1381 4296 4296 1 3075 1 4946 1 2896 2896 1510 1 3204 4126 3204 3204 3204 4861 4861 1 314 1 4117 1 3856 1 3280 1 4754 1 3363 1 4732 47...
result:
ok 5000 numbers
Test #37:
score: 0
Accepted
time: 37ms
memory: 11980kb
input:
4569 3992 843 844 4391 4392 4463 4464 4103 4104 2319 2320 3829 3830 3081 3082 2981 2982 667 668 1445 1446 3429 3430 2609 2610 4225 4226 741 742 755 756 3605 3606 579 580 1479 1480 25 26 191 192 1681 1682 2455 2456 2559 2560 467 468 525 526 1541 1542 1595 1596 1051 1052 1923 1924 2191 2192 1261 1262 ...
output:
1868 1868 2796 4085 4085 3910 3910 2796 4490 4528 4528 4528 4528 4528 4528 4312 2665 1 3985 1 1387 4113 4113 3333 1387 2291 1387 1 2071 1 4077 4077 4077 4077 4077 1599 967 1 2469 4205 2469 1 3117 3117 1789 3969 3969 3969 3969 3969 3969 3969 3969 3969 3969 3969 3969 3912 3007 1 2938 1 3522 1 1618 1 3...
result:
ok 3992 numbers
Test #38:
score: 0
Accepted
time: 44ms
memory: 12044kb
input:
5000 5000 1611 1612 2733 2734 3021 3022 2221 2222 375 376 1115 1116 1713 1714 567 568 1013 1014 2739 2740 841 842 4561 4562 2961 2962 2921 2922 1269 1270 4135 4136 3663 3664 3871 3872 1237 1238 4633 4634 2475 2476 381 382 4725 4726 2877 2878 3259 3260 4335 4336 4417 4418 3943 3944 2025 2026 1485 148...
output:
3813 3813 3813 3835 3835 4493 4493 4493 4493 4493 3813 3813 2299 1 4906 4906 3731 4893 4893 4893 4893 4893 4893 4893 4893 4893 4893 4893 4893 3824 3824 1 3749 3749 3749 3749 3960 4653 3960 3960 3749 1 1828 4250 4250 2794 1828 3464 1828 1 4698 4698 650 1 4461 4461 4461 1 1972 4117 4117 3835 4238 4238...
result:
ok 5000 numbers
Test #39:
score: 0
Accepted
time: 30ms
memory: 12216kb
input:
4077 3960 39 40 947 948 1193 1194 893 894 229 230 1571 1572 1829 1830 211 212 3 4 837 838 173 174 1819 1820 685 686 3629 3630 1185 1186 689 690 3211 3212 667 668 367 368 1759 1760 3117 3118 1803 1804 2525 2526 1497 1498 3707 3708 3817 3818 165 166 2101 2102 4043 4044 2461 2462 1733 1734 1821 1822 10...
output:
3613 3613 3773 3773 3773 3773 3773 3773 3773 3773 3773 3773 3773 3773 3773 3773 3773 1 1589 1 1466 1466 390 1 3703 3703 3703 3703 3243 3243 3419 3419 3419 4048 4048 3419 3419 3243 3830 3830 3243 1 3601 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 3715 371...
result:
ok 3960 numbers
Test #40:
score: 0
Accepted
time: 42ms
memory: 12024kb
input:
5000 5000 4471 4472 2627 2628 4695 4696 2617 2618 1159 1160 117 118 2669 2670 1455 1456 519 520 597 598 1761 1762 3631 3632 2001 2002 2639 2640 913 914 4111 4112 4517 4518 2103 2104 1307 1308 4995 4996 801 802 2013 2014 2307 2308 1391 1392 1259 1260 2333 2334 2365 2366 3885 3886 4977 4978 2997 2998 ...
output:
4194 4194 4972 4972 4972 4978 4978 4978 4978 4978 4978 4978 4978 4978 4978 4978 4978 4978 4978 4978 4978 4978 4978 4994 4994 4994 4994 4978 4978 4978 4978 4978 4978 4978 4978 4857 4857 4857 4857 4857 4597 4896 4896 4896 4795 4795 4795 4795 4795 4795 4795 4795 4795 4795 4795 4795 4795 4795 4795 4795 ...
result:
ok 5000 numbers
Test #41:
score: 0
Accepted
time: 19ms
memory: 12284kb
input:
3642 3651 2435 2436 2655 2656 277 278 2569 2570 925 926 2613 2614 3545 3546 915 916 3625 3626 1627 1628 1915 1916 3249 3250 2887 2888 2451 2452 405 406 1385 1386 2625 2626 2403 2404 3579 3580 2453 2454 2085 2086 649 650 2891 2892 979 980 2507 2508 3571 3572 1651 1652 2793 2794 2377 2378 643 644 2145...
output:
2030 3535 3535 3535 3535 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3628 3573 3383 3383 3383 3383 3383 3383 3383 3383 3383 3383 3476 3476 3476 3383 2922 2922 2922 2922 2922 2797 3581 ...
result:
ok 3651 numbers
Test #42:
score: 0
Accepted
time: 51ms
memory: 12060kb
input:
5000 5000 1447 1448 1677 1678 2235 2236 37 38 3595 3596 625 626 835 836 3063 3064 4035 4036 3165 3166 3827 3828 1277 1278 4599 4600 1977 1978 411 412 4897 4898 3289 3290 1549 1550 4149 4150 3831 3832 2635 2636 3735 3736 1105 1106 1779 1780 2117 2118 695 696 377 378 2359 2360 1575 1576 1731 1732 1319...
output:
4827 4827 4827 4827 4827 4827 4827 4827 4827 4827 4827 4310 4453 4310 4310 4347 4310 4310 3212 3212 3008 1 2907 2907 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 4745 474...
result:
ok 5000 numbers
Test #43:
score: 0
Accepted
time: 28ms
memory: 11980kb
input:
4221 3506 533 534 1071 1072 505 506 569 570 1297 1298 2019 2020 1545 1546 3095 3096 3557 3558 2159 2160 3315 3316 1711 1712 803 804 1755 1756 2921 2922 2385 2386 3723 3724 4007 4008 447 448 3149 3150 669 670 3121 3122 235 236 1025 1026 3719 3720 709 710 385 386 1825 1826 4179 4180 4031 4032 2437 243...
output:
3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3725 3791 3791 3791 3791 3941 3941 3941 4094 4094 4094 4189 4189 4189 4189 4189 4189 4189 4189 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 4211 ...
result:
ok 3506 numbers
Test #44:
score: 0
Accepted
time: 54ms
memory: 11980kb
input:
5000 5000 4195 4196 2865 2866 759 760 1939 1940 4359 4360 3335 3336 2621 2622 4283 4284 2235 2236 3829 3830 4479 4480 3273 3274 725 726 867 868 329 330 2597 2598 4817 4818 1507 1508 1845 1846 2117 2118 3449 3450 515 516 3989 3990 3733 3734 121 122 379 380 1501 1502 3739 3740 1505 1506 3639 3640 989 ...
output:
1967 1967 2815 3841 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 4945 ...
result:
ok 5000 numbers
Test #45:
score: 0
Accepted
time: 43ms
memory: 11888kb
input:
5000 5000 545 546 1869 1870 143 144 1969 1970 1013 1014 2703 2704 3507 3508 2091 2092 4957 4958 2055 2056 4097 4098 1769 1770 1301 1302 1537 1538 3911 3912 2691 2692 4719 4720 105 106 1561 1562 1925 1926 1563 1564 4673 4674 2907 2908 3049 3050 725 726 1287 1288 1671 1672 2277 2278 3921 3922 4021 402...
output:
3679 1 4331 1 3599 1 1735 1 4832 1 2596 1 4350 1 3331 1 3217 1 4699 1 3493 1 3832 1 4492 1 4293 1 4142 1 3301 1 2004 1 4621 1 4317 1 3763 1 4715 1 2752 1 1569 1 4837 1 2893 1 4100 1 845 1 3123 1 4821 1 4349 1 1858 1 4927 1 4816 1 719 1 1560 1 2731 1 2450 1 3459 1 1212 1 4974 1 2346 1 4305 1 2616 1 2...
result:
ok 5000 numbers
Test #46:
score: 0
Accepted
time: 43ms
memory: 12016kb
input:
5000 5000 2393 2394 4967 4968 1659 1660 925 926 4519 4520 257 258 859 860 67 68 3677 3678 419 420 4977 4978 849 850 1483 1484 4403 4404 3349 3350 3525 3526 165 166 629 630 2597 2598 815 816 4059 4060 229 230 2927 2928 3441 3442 763 764 1549 1550 4729 4730 1393 1394 901 902 3661 3662 2065 2066 3377 3...
output:
456 456 456 456 462 469 469 469 469 469 469 469 469 469 469 469 469 469 469 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 498 ...
result:
ok 5000 numbers
Test #47:
score: 0
Accepted
time: 48ms
memory: 12012kb
input:
5000 5000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1 5000 1...
result:
ok 5000 numbers
Subtask #4:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #48:
score: 0
Time Limit Exceeded
input:
92958 98464 51219 9529 5310 48981 12657 92722 17683 1969 89122 57994 77115 3985 89329 58436 62960 78863 60463 13809 76207 73216 80590 37997 64129 20857 37000 82851 34428 54499 6939 6207 23897 3322 74613 92701 34910 46456 34956 70002 9221 54471 63095 49941 8885 74051 55498 18672 17692 60440 32870 351...
output:
92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 92956 ...