QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#790640 | #1400. Water Bottle | modwwe | 100 ✓ | 737ms | 230812kb | C++23 | 4.8kb | 2024-11-28 14:22:12 | 2024-11-28 14:22:12 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while (c < '0' || c > '9')
{
c = getchar_unlocked();
}
while (c >= '0' && c <= '9')
{
x = (x << 1) + (x << 3) + c - '0';
c = getchar_unlocked();
}
return x;
}
void phongbeo();
const int inf = 1e9;
const ll mod2 = 1e9 + 7;
const int mod1 = 998244353;
const ll base=67;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int add(int x,int y)
{
if(x+y>=mod2) x-=mod2;
if(x+y<0)x+=mod2;
return x+y;
}
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a, b, c;
};
struct id
{
int a, b, c, d;
};
struct ie
{
int a, b, c, d, e;
};
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,t,lim,w,l,r ;
int kk;
int el = 19;
main()
{
if(fopen(task".inp","r"))
{
fin(task);
fou(task);
}
NHP
/// cin>>s1;
// modwwe
phongbeo();
// checktime
}
bool cmp(ic a,ic b)
{
return a.c<b.c;
}
int query;
int dist[2001][2001];
int b[2001][2001];
bool a[2001][2001];
int st[18][200001];
int cost[18][200001];
int in[200001];
int ou[200001];
vector<ic> v;
vector<ib> ke[200001];
deque<id> p;
struct ds
{
ib dsu[200001];
void reset(int x)
{
dsu[x]= {1,x};
}
int get(int x)
{
if(dsu[x].b==x) return x;
return dsu[x].b=get(dsu[x].b);
}
bool noi(int x,int y)
{
x=get(x);
y=get(y);
if(x==y) return 0;
if(dsu[x].a<dsu[y].a) swap(x,y);
dsu[x].a+=dsu[y].a;
dsu[y].b=x;
return 1;
}
} ds;
void dfs(int x,int y)
{
st[0][x]=y;
in[x]=++dem;
for(auto f:ke[x])
if(f.a^y)
{
dfs(f.a,x);
cost[0][f.a]=f.b;
}
ou[x]=dem;
}
bool check(int x,int y)
{
if(in[x]<=in[y]&&in[y]<=ou[x]) return 1;
return 0;
}
int lca(int x,int y)
{
int s=0;
if(check(x,y)) return 0;
for(int i=17; i>=0; --i)
if(!check(st[i][x],y))
{
s=max(s,cost[i][x]);
x=st[i][x];
}
s=max(s,cost[0][x]);
return s;
}
int solve(int x,int y)
{
if(ds.get(x)!=ds.get(y)) return -1;
return max(lca(x,y),lca(y,x));
}
void phongbeo()
{
cin>>n>>m>>k>>query;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
char x;
cin>>x;
if(x=='.') a[i][j]=1;
else a[i][j]=0;
}
for(int i=1; i<=k; i++)
{
ds.reset(i);
cin>>l>>r;
p.push_front({0,l,r,i});
}
while(!p.empty())
{
id x=p.front();
p.pop_front();
if(b[x.b][x.c]!=0) continue;
b[x.b][x.c]=x.d;
dist[x.b][x.c]=x.a;
for(int j=0; j<4; j++)
{
l2=x.b+dx[j];
r2=x.c+dy[j];
if(l2<=n&&l2>0&&r2<=m&&r2>0&&a[l2][r2]&&b[l2][r2]==0)
p.pb({x.a+1,l2,r2,x.d});
}
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
for(int f=0; f<4; f++)
{
l2=i+dx[f];
r2=j+dy[f];
if(l2<=n&&l2>0&&r2<=m&&r2>0&&b[l2][r2]!=b[i][j]&&min(b[i][j],b[l2][r2])!=0)
v.pb({b[l2][r2],b[i][j],dist[i][j]+dist[l2][r2]});
}
sort(v.begin(),v.end(),cmp);
for(auto x:v)
if(ds.noi(x.a,x.b))
{
ke[x.a].pb({x.b,x.c});
ke[x.b].pb({x.a,x.c});
}
for(int i=1; i<=k; i++)
if(!in[i])
{
dfs(i,0);
}
ou[0]=dem;
for(int i=1; i<18; i++)
for(int j=1; j<=k; j++)
{
st[i][j]=st[i-1][st[i-1][j]],
cost[i][j]=max(cost[i-1][j],cost[i-1][st[i-1][j]]);
}
while(query--)
{
cin>>l>>r;
cout<<solve(l,r),down
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 4ms
memory: 67544kb
input:
59 200 200 2000 #...#.#...##.##.....#......##...#.#.#....#...........###.##.#.....###.#.##...##..#..........#..........##..#.......#...#.#...#.....#......#.#....##...##..#....#......#.#.#....#...#.#.......#.....#..#. #..##...#..##..#..#.##............#........##.#....#.........#...##.#.................
output:
11 0 12 12 12 11 13 13 13 7 11 13 13 13 13 13 13 13 12 8 10 12 13 13 13 17 13 12 13 12 13 13 13 10 12 13 13 8 12 13 12 13 13 11 13 13 12 13 12 19 11 13 13 13 13 13 13 6 12 13 13 13 12 7 17 12 13 13 12 12 13 13 11 12 13 12 11 13 13 13 13 13 13 11 12 10 13 12 11 13 13 12 13 13 12 12 8 13 8 13 11 13 13...
result:
ok 2000 lines
Test #2:
score: 10
Accepted
time: 3ms
memory: 68264kb
input:
198 77 200 2000 ............##......#..........#.....##.....#...#......#......##..........#.. ##..#..##..............#..........####.........##.........#....#.#.........#. #..##.....#....##.#..#.#..##.....#.#....#..#....#...#.#.##.....#.#.#.......#. ....#...#.#......#..#......##.....#..#...............
output:
11 5 13 16 11 11 12 12 14 12 12 12 13 12 12 12 12 11 12 17 13 10 14 11 12 13 13 14 13 13 16 14 12 12 13 12 13 15 12 12 12 14 12 13 14 14 10 12 11 13 13 13 11 13 13 12 11 14 12 11 16 13 13 11 13 13 14 13 12 13 13 12 12 12 12 16 12 13 21 13 13 12 12 13 11 11 11 11 13 11 12 12 12 16 12 14 12 13 13 15 1...
result:
ok 2000 lines
Test #3:
score: 10
Accepted
time: 3ms
memory: 72528kb
input:
200 200 200 2000 ###.##.#..#.##..#....###............#...#............#....###...#.#.#....#..##.#..#.#..##.###..#.##...######.##..#..#....###..#....#..#.##...###.#..##..#.....#.#.#.#####....#...#...##..#..#.#......... ###..##.....#.#..#..###..##.#..###..#...#....#.#.....##.#..#...###..#..........#.....
output:
32 32 32 32 25 24 30 39 35 33 24 32 29 28 7 32 -1 32 32 29 28 32 32 20 33 30 32 39 36 43 24 34 32 -1 24 43 32 43 28 39 27 32 17 30 30 27 30 25 30 28 39 32 32 28 28 28 32 30 35 34 30 32 28 23 32 32 39 21 30 39 29 30 30 34 30 32 30 32 30 32 19 24 30 32 23 28 28 32 28 32 -1 30 11 29 32 24 32 30 30 32 3...
result:
ok 2000 lines
Test #4:
score: 10
Accepted
time: 39ms
memory: 70400kb
input:
200 200 200 200000 ...#..#..#.##................#.....#..##..#....#.##..#..........#..#.#..#.....###..#........#....#..#...#.#..##.###...##.........#.......##..#..#.....##..........#.#.............##.#.#.....##.#....... ........#.........#...####...#.#.......#..##.##.####..##..####.###...#..##...#.....
output:
34 33 30 19 30 30 33 30 35 32 19 35 30 35 28 30 30 30 30 30 35 -1 28 30 30 35 -1 26 30 35 -1 34 25 35 28 28 28 30 35 33 35 23 30 30 14 27 35 30 28 35 30 35 32 23 30 35 30 28 26 24 30 28 34 28 30 30 35 35 23 33 28 17 18 30 33 24 35 -1 33 30 33 33 28 33 18 33 35 30 30 15 35 28 26 -1 -1 24 33 28 30 23 ...
result:
ok 200000 lines
Test #5:
score: 10
Accepted
time: 35ms
memory: 70748kb
input:
200 199 200 200000 ...#..##.#.#...#...#.##.....###...##....#...#.......#...##...#....#.#.##.###...#...#...#............#.......#..#...#.#.#....#....#...#......##.....#....#..##.......#..##.#......#...#......#...#..#... #....##.#.#..#.#...#...#.......#.##...#......#....##.#..###......#.#..##.....#.#....
output:
22 30 30 25 30 30 25 30 -1 22 30 30 21 15 30 30 25 19 -1 30 30 30 25 30 25 30 30 30 30 30 30 30 21 30 30 30 30 20 25 30 21 25 30 30 30 30 30 30 30 30 30 25 20 30 30 30 30 30 30 30 30 30 21 -1 30 23 25 -1 20 30 30 30 30 30 30 8 30 30 19 24 25 -1 30 30 30 30 25 30 25 25 19 21 25 30 23 30 25 28 25 30 -...
result:
ok 200000 lines
Test #6:
score: 10
Accepted
time: 41ms
memory: 70320kb
input:
200 200 200 200000 ..##....#...#...#....###.##.#....#.#.....#..#.##...#####.##.#.....#...###.#..........##.#......##....#..##.#..##...#.#...#......##.##.......#.#.##.##....##.#.#..........######.#....................##. ..#...#.#.#...#..##.#..#...#....#.#..........#......##.#..##...#...#..#...#........
output:
25 25 23 22 13 25 25 25 25 23 22 -1 25 25 22 25 27 22 22 17 16 25 27 10 25 22 22 25 25 23 21 22 25 25 25 27 25 23 13 21 25 27 25 22 25 -1 16 25 31 22 23 25 23 27 23 25 -1 27 22 21 23 23 23 21 -1 25 25 25 23 25 23 -1 25 25 25 -1 -1 21 -1 27 -1 25 12 25 -1 22 31 22 18 23 25 25 25 27 -1 25 25 25 25 21 ...
result:
ok 200000 lines
Test #7:
score: 10
Accepted
time: 34ms
memory: 70708kb
input:
200 200 200 200000 .#.#...#....#.#..##.#..#.######..#.##......#..#.#....####.#..#.#.#.#....#........#..#..#.....#.##...#..#.#......##.##...#......###..##.##....###..##.#.#.#......#..##...#..#.#..#...#...........#....... #.....##......#.#..##.#....#..#...#.#.#..#...#......#...##...............#...#.#...
output:
-1 -1 21 21 -1 21 -1 17 21 -1 13 15 -1 -1 16 21 21 16 14 17 16 21 21 17 17 -1 21 21 21 -1 21 21 17 49 24 39 21 21 21 17 13 23 15 21 12 16 21 17 13 21 21 -1 21 21 16 -1 20 15 -1 16 -1 -1 15 21 21 16 14 17 21 24 21 21 15 20 16 16 -1 39 16 16 -1 21 17 21 24 16 16 16 21 21 20 -1 39 -1 21 -1 20 21 17 -1 ...
result:
ok 200000 lines
Test #8:
score: 10
Accepted
time: 39ms
memory: 70500kb
input:
200 200 200 200000 ........................................................................................................................................................................................................ .###############################################################################...
output:
13 1373 7016 7016 7016 15 7016 7016 13 7016 7016 13 7016 7 10 1373 10 7016 7016 14 7016 7016 7016 11 7016 20 7016 13 7016 13 11 7016 7016 13 7016 10 7016 11 7016 16 12 7016 7016 10 21 7016 7016 13 7016 7016 7016 14 13 11 11 7016 19 14 14 14 7016 13 16 13 13 14 7016 16 7016 11 7016 14 7016 7016 10 70...
result:
ok 200000 lines
Test #9:
score: 10
Accepted
time: 40ms
memory: 70576kb
input:
200 200 200 200000 ........................................................................................................................................................................................................ .###############################################################################...
output:
500 440 440 500 500 440 500 324 234 500 500 324 291 500 440 500 500 440 500 67 217 181 500 335 500 500 179 440 46 324 440 324 500 500 500 440 440 335 500 324 440 324 500 213 151 500 440 153 324 291 500 143 500 440 500 440 193 200 440 500 324 324 324 500 440 440 272 324 500 324 192 500 500 39 335 192...
result:
ok 200000 lines
Subtask #2:
score: 30
Accepted
Test #10:
score: 30
Accepted
time: 12ms
memory: 107768kb
input:
2000 100 1000 1 ..##...........#..#....#.####...#...#....#.........#.#..#.#.######.##..#..#......#..#..##.#..#.##... .........##..#.####.###..#......#.#...#.....#......#..#..#...#.##...##..##...#.#..####.##.#........# .....#.....................##...#..#..#.#........#.#...#.#...###.....#...#.#.........
output:
40
result:
ok single line: '40'
Test #11:
score: 30
Accepted
time: 27ms
memory: 74876kb
input:
200 2000 5000 1 ...#..#.##.#.#.#..#...#..#....#.##....##...#.......#.......#.##.#......#....##.##.....#.##.#.#........#..#.#..#...#.##...#..#....##.....#....##..#...##..#......#...#.#....##..##.#...##.....#......##....#.#....#..##.##..#.....##......#..#..#.....##.#..#.#..#.....##.#.#.##...##...#.......
output:
21
result:
ok single line: '21'
Test #12:
score: 30
Accepted
time: 243ms
memory: 131972kb
input:
2000 2000 5000 1 ..##..#.###..#.####........##.#..##..####..#.#..#.#....#.##.#..##.##...###....##...##...##..#..####....#.##..###..##.##.##..##..####..#.##..#.#..#..##........##....#.#....##..#...##....##.##...######..#......####..#..#.#.#..##.##....#.##.#..##..##..#.###.#.##.....##.....#...#.#....#...
output:
144
result:
ok single line: '144'
Test #13:
score: 30
Accepted
time: 319ms
memory: 138956kb
input:
1988 2000 5000 1 ......#....#..#........###....#..#..#...#...##......#.##..#..#.....#....#....#.##.##...#...#.##.......###..#..#.#..##...#.#..#.##.##.....##.#........#.#..##.#...####.#...##.###.......#.....#...###.#....###..#...#.....#.#.#...#....#..#..#....#..#.#.#.#..#.#..#.......##....#.#..#..#.#...
output:
52
result:
ok single line: '52'
Test #14:
score: 30
Accepted
time: 338ms
memory: 142724kb
input:
2000 2000 5000 1 .........#.#......###..................#......#.......##..#.....#.#.####.#...#.##..........#..##...#.#.#.#.#..#.#..##...#...##....#...#..#......#.#.#................##...#..#...........##.##...........#...#..#..#.##......#.....#.###.......#..............................###......#......
output:
48
result:
ok single line: '48'
Test #15:
score: 30
Accepted
time: 251ms
memory: 131412kb
input:
2000 2000 5000 1 ..#....#....#.#.##...#.###.##.#..##.####.......#.#..##...##.#.#.#..##.#.##...#.#.##..#.#..#........#........##....#.....#..#..#...##..###..#......#####.###.##.....#...#..##...#..#..#..#...#.....#.#...######......##...##..###.#####...##.#..#...#..##..#......#..#.#.###......#..##.#.#....
output:
-1
result:
ok single line: '-1'
Test #16:
score: 30
Accepted
time: 311ms
memory: 138456kb
input:
2000 1987 5000 1 #......#....#.#.....#.#...#.........#...##......##....##......#.#...##.##.#....#..#...#...#.......##...#....#.......#.......#....#....##.....##..#.#.....###...##...............##....#....#####.#....##...#.#.#.....##.#.##........####........##.#..##...##....#...#...##..##.###..#........
output:
51
result:
ok single line: '51'
Test #17:
score: 30
Accepted
time: 321ms
memory: 143120kb
input:
2000 2000 5000 1 ..............##.........#.#...............#....#...#....##.###.....#.##.#.#..#...#.......#..#............#....#.###..#.......#.##...#........#...#..#.#.#.....###....................#.......##.....#..#......#..........#.#.#.................##....#........#...#..#.##..#..........#.#....
output:
49
result:
ok single line: '49'
Test #18:
score: 30
Accepted
time: 279ms
memory: 153728kb
input:
2000 1995 5000 1 ..................................#...#.......................................#..................................#......................................................................#....#...................#.......................#....................................................
output:
44
result:
ok single line: '44'
Test #19:
score: 30
Accepted
time: 297ms
memory: 132144kb
input:
2000 2000 500 1 .........#...#...#..#..#..#..##...##...#.#..#...##.....#..#..#..##.#..###.#..#..#.##.............#.#.#..#...#....#.#.....##.###...##.#.....#..#..##..#.###...###...#........##.#..#.#..###.......##...#..##...#...###...#.#....#.....####....#.....#..#...#...#..#.....#..#......##.#.....#....
output:
166
result:
ok single line: '166'
Test #20:
score: 30
Accepted
time: 306ms
memory: 135084kb
input:
2000 2000 2000 1 .#..#..#....#.#..#.#..#.#####......###......#......#..#.........#.##....#..#.....#.#.......###.......#............##...#..##...#.#...#..#...#......#...#..#......#..............#.##.........#.....#....#.......#.#.......##...#.#...#......#.....#..#.......##..#....##.....#.....#.#........
output:
81
result:
ok single line: '81'
Test #21:
score: 30
Accepted
time: 99ms
memory: 127160kb
input:
2000 2000 5000 1 ..............................................................................................................................................................................................................................................................................................
output:
13
result:
ok single line: '13'
Test #22:
score: 30
Accepted
time: 136ms
memory: 120364kb
input:
2000 2000 5000 1 ..............................................................................................................................................................................................................................................................................................
output:
2365
result:
ok single line: '2365'
Test #23:
score: 30
Accepted
time: 104ms
memory: 126412kb
input:
2000 2000 5000 1 ..............................................................................................................................................................................................................................................................................................
output:
1062003
result:
ok single line: '1062003'
Test #24:
score: 30
Accepted
time: 139ms
memory: 121568kb
input:
2000 2000 5000 1 ..............................................................................................................................................................................................................................................................................................
output:
2247
result:
ok single line: '2247'
Subtask #3:
score: 30
Accepted
Dependency #2:
100%
Accepted
Test #25:
score: 30
Accepted
time: 19ms
memory: 108072kb
input:
2000 100 1000 1000 #.....##.....#..##..........#....#..#..##.#..#....#..##..#...#......#....###.#.#..#...##..#....##... ##.#.#...#.####..#.#..#.#........##..........#..#....##..#.......#..........###..#.#..#..........#.. ...##...##..##.#....#.#..#......#........####.#....#.##.#.#..#.#..#........#......
output:
31 34 33 31 22 37 33 31 33 33 30 -1 34 34 30 33 33 31 31 33 37 33 31 28 33 33 31 31 31 33 31 33 33 30 35 33 33 30 33 31 26 33 33 30 32 31 33 24 -1 31 30 33 33 -1 -1 32 33 31 31 33 30 33 -1 22 33 37 33 33 31 33 -1 33 28 37 24 33 33 33 30 32 33 31 34 18 33 33 31 25 33 24 33 30 33 26 30 30 30 31 33 35 ...
result:
ok 1000 lines
Test #26:
score: 30
Accepted
time: 34ms
memory: 73312kb
input:
200 2000 1000 1000 ...#..#...##.....##..#.####....###.#......#..#...#...........##.#....#.#...#.#...#...##...#.##...####..............#.##...##.......#.......#.#....###...#.#..#............#.....#.....#.#.##.#..#.#..#......#....###...................#.....#.##..#......#...#..#.##.#...#.........#.#.....
output:
47 29 41 48 35 35 47 39 39 47 -1 35 47 47 40 33 35 47 32 41 47 47 47 47 30 32 44 47 47 47 -1 41 41 47 40 47 47 41 -1 47 41 47 44 -1 41 -1 47 47 47 47 47 35 47 43 35 39 47 42 41 41 44 47 42 41 47 40 47 44 41 35 47 41 47 41 44 47 47 35 47 47 35 40 -1 41 41 42 39 50 47 47 43 47 47 47 47 41 41 47 47 47 ...
result:
ok 1000 lines
Test #27:
score: 30
Accepted
time: 227ms
memory: 128808kb
input:
2000 2000 500 10000 ##...####.#.#.##........###..##..##.......#......###.....#....#....##........#####.....#..##.##.......#.##......#....###...#.#.###.#...##.....##..###...#..#....#..##.#.#..###...#.....#.#........##...#.#.##.......#..##.........#...##..#.####...#...#...#.#.###.#.###....#..#..#..#.....
output:
-1 -1 323 392 -1 -1 -1 391 392 -1 392 613 355 392 -1 -1 -1 408 392 613 -1 -1 -1 -1 -1 392 408 -1 -1 271 296 350 295 -1 392 -1 -1 -1 -1 -1 -1 323 -1 350 -1 480 350 -1 -1 392 -1 -1 -1 408 296 -1 -1 -1 -1 -1 613 -1 -1 -1 -1 613 -1 392 -1 392 295 -1 296 -1 296 -1 -1 613 613 613 408 613 -1 408 350 -1 295...
result:
ok 10000 lines
Test #28:
score: 30
Accepted
time: 317ms
memory: 137144kb
input:
1988 2000 5000 10000 ..#.#.##.........###...#...#......###..........#..#.#........##.###....#..#.#.......##....##.#####.......#..........#..##..#.....##..##.........##..#.....#..##................#.###...#....###.#.#.##.......####................#.....#..##....###......###.#..........##.#..##.##..#....
output:
51 54 53 54 53 54 65 50 54 52 50 53 57 51 53 53 54 51 49 54 53 59 54 51 54 51 54 54 48 53 56 54 58 56 -1 53 55 55 55 51 53 56 -1 53 53 53 47 60 51 51 54 52 54 56 53 53 48 54 51 53 54 45 49 52 53 51 53 54 54 51 49 53 54 -1 54 53 53 53 51 49 -1 50 48 49 48 54 53 58 -1 54 52 -1 51 53 43 51 -1 44 48 52 ...
result:
ok 10000 lines
Test #29:
score: 30
Accepted
time: 318ms
memory: 147304kb
input:
2000 2000 5000 10000 ...#....#........#.......##..#..#....##.#......#........##..#.##.###....##..#..#.#......#.....#.#.....................#..........#...#..#.......##.....#.#....#............#....##...#......##.#.#....##.......#.....#..#.............#.#......#...#.........#.#........####..........#...
output:
43 43 44 40 41 43 44 44 47 44 45 50 45 44 44 45 44 42 41 37 44 44 43 42 45 48 44 45 43 45 45 48 44 45 44 44 47 36 44 45 44 41 50 44 47 50 43 48 42 44 47 44 47 44 44 39 45 40 47 40 43 48 47 44 45 44 53 45 46 44 41 43 45 44 43 56 43 44 43 44 44 49 43 55 45 45 49 47 45 44 45 44 45 43 67 45 47 44 43 44 ...
result:
ok 10000 lines
Test #30:
score: 30
Accepted
time: 288ms
memory: 156776kb
input:
2000 1995 5000 10000 ...................................................................................................................................................................................................................................................................#......................
output:
40 40 41 40 44 41 47 40 41 40 40 40 41 40 55 40 41 42 41 48 40 40 48 40 40 45 40 41 40 40 40 41 38 40 41 41 37 44 41 40 48 34 40 39 42 40 36 42 41 41 44 40 41 41 40 39 41 41 39 37 42 41 48 41 40 41 40 41 40 43 39 41 40 40 41 46 46 41 48 41 40 40 38 40 40 40 37 41 40 41 41 34 41 41 40 47 42 38 40 40 ...
result:
ok 10000 lines
Test #31:
score: 30
Accepted
time: 289ms
memory: 132328kb
input:
2000 2000 500 10000 #..#...#....#......##...#.....#.#..#.....#......#....#....#####.....#.....#..##...........####..#.##.#.#.#.#..#...#.......#.#...#.#..#.##.#...#.......##.#...##...#..##..###...#.#....#.#..#..##..##......#.....#.#..........#...#....#......#...........#..#..#.#.#......#.##..#.#........
output:
159 161 161 161 161 -1 74 161 161 153 -1 140 161 152 151 161 154 161 168 159 161 161 139 132 161 188 188 152 146 161 159 153 -1 153 134 153 168 161 154 153 161 131 6647 190 161 188 147 153 153 147 161 161 161 -1 140 161 168 168 161 153 -1 168 161 168 163 161 153 161 158 153 168 161 161 132 161 155 6...
result:
ok 10000 lines
Test #32:
score: 30
Accepted
time: 321ms
memory: 138660kb
input:
2000 2000 5000 10000 ##........#.#..##.....#.#..####..####.....#...##...##...#..#...##..#...#...##..#.#...#..####....#.....##...#..#...#..#....#.#..##..........#.......#.#.....###...##....###.#.#...#...###.#..##..##....#.......#...#.#..##.....#...#......#..#...#.##...#......#.##..##.....#.##..#.#......
output:
51 44 30 48 52 66 49 49 48 46 29369 48 55 52 53 53 52 50 48 51 66 49 48 54 49 66 55 55 66 49 49 50 49 51 55 53 55 47 43 -1 47 55 55 58 58 48 66 50 -1 50 49 49 53 36 55 49 72 53 55 50 66 53 53 66 51 50 53 49 50 55 49 53 53 49 56 50 55 50 53 55 51 49 66 66 51 49 45 48 -1 54 53 51 48 49 48 34 45 57 52 ...
result:
ok 10000 lines
Test #33:
score: 30
Accepted
time: 109ms
memory: 127032kb
input:
2000 2000 5000 10000 ..........................................................................................................................................................................................................................................................................................
output:
307123 13 307123 12 11 307123 13 15 15 307123 307123 307123 307123 13 307123 9 307123 13 12 307123 307123 307123 13 13 13 307123 307123 307123 307123 13 307123 11 14 307123 13 13 307123 307123 13 15 307123 13 307123 15 307123 307123 307123 307123 14 307123 307123 307123 307123 13 307123 307123 30712...
result:
ok 10000 lines
Test #34:
score: 30
Accepted
time: 134ms
memory: 121604kb
input:
2000 2000 5000 10000 ..........................................................................................................................................................................................................................................................................................
output:
2553 2553 3132 2234 2270 3132 2234 3132 2802 3132 2234 2802 2214 3132 1187 3132 3132 3132 2802 2802 1905 2179 3132 3132 1714 2234 2742 2802 3132 2595 2553 1722 2802 2362 2214 2802 3132 2553 1413 2802 3132 2802 2802 2553 1517 2802 2802 2802 3132 2553 2553 3132 2553 1929 2802 2553 2553 3132 3132 2802 ...
result:
ok 10000 lines
Test #35:
score: 30
Accepted
time: 128ms
memory: 116960kb
input:
2000 2000 5000 10000 ..........................................................................................................................................................................................................................................................................................
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 10000 lines
Subtask #4:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #36:
score: 30
Accepted
time: 309ms
memory: 132004kb
input:
1997 2000 10000 200000 ..##......#...#.......#.#..##..##..##.#............#.#.##.###.##.##.#.##...#.#.##.######.#.##.#...#.##......#....#..#.#.##.#......#.##.##.#..#.#...###.........#..#....##..#..#.###.##.#..##........##..##....#...##.##..##.#.#.#..##..###..#...#..##.#....##.#...###...#.##..#.#.......
output:
-1 76 84 91 96 -1 107 67 -1 72 84 74 107 -1 -1 -1 108 79 83 98 -1 141 -1 -1 84 -1 -1 -1 98 -1 -1 118 -1 76 -1 84 72 -1 -1 -1 98 99 -1 -1 74 73 68 98 -1 118 90 77 -1 -1 -1 107 -1 -1 84 -1 84 98 74 90 96 84 -1 -1 -1 88 75 -1 98 -1 -1 98 -1 72 73 98 85 -1 98 -1 84 -1 98 -1 -1 -1 87 98 93 -1 107 -1 76 -...
result:
ok 200000 lines
Test #37:
score: 30
Accepted
time: 529ms
memory: 175032kb
input:
2000 2000 200000 200000 ##......#..#..##.##.###.#.#..##.#.###..##.###..###.....##.#..#.....#...#.#...###..#..##.##...##.#....#...............#..#..##..#.#.....#.#.####.##.#..#.#..#..#....###...##.......#.#...##..#..#..##.#...##...##.#.#..####.#...#.#.#.##..#....#.....##..##...#.#.###...####..###.#.#...
output:
-1 16 16 16 -1 16 16 -1 17 16 16 16 16 -1 -1 16 18 16 -1 16 -1 16 16 14 15 18 -1 16 19 -1 19 16 26 -1 16 -1 16 17 16 16 21 16 -1 16 23 16 18 -1 16 16 15 16 16 15 18 -1 16 16 -1 17 16 16 -1 16 16 17 26 17 -1 -1 -1 -1 -1 16 -1 -1 16 17 16 16 -1 -1 16 18 -1 14 16 -1 15 -1 15 13 -1 14 -1 16 -1 16 22 -1 ...
result:
ok 200000 lines
Test #38:
score: 30
Accepted
time: 295ms
memory: 132104kb
input:
2000 2000 500 2000 .......#....#..##.##..#......#.#....##.....#....#...........#.#......##....#...#...#.#.##.#....#.....#.#..#..#...#.#...#.......#..#.#..#.........#..#.#.....##.##......#.#..#.#.......#...........#...#.##..##.#....###..###..#...#..###..#..#..#.....#................#...#......##..#.....
output:
161 161 141 139 199 165 169 169 150 139 167 161 165 117 155 167 199 167 161 167 168 161 165 -1 135 199 161 165 165 165 161 168 170 161 167 161 199 161 167 167 186 161 161 161 200 167 167 158 158 -1 139 129 199 161 161 167 158 193 167 165 199 186 161 161 167 168 167 167 148 165 161 156 165 167 158 16...
result:
ok 2000 lines
Test #39:
score: 30
Accepted
time: 709ms
memory: 194100kb
input:
2000 1998 200000 200000 .#...#....#...#...###....##.#..#.......#................##.#..##.#.#.##.###..#...#..#...###...#.#...##........#.............#....#...#...#...#...###.#.#........##.#...#..##...#...#..#....###.....#.##........#.#.#.#...#..#.##..#..#....#....#..#..#......###....#.##.#..#.#.#..##...
output:
8 8 11 12 8 8 8 8 8 8 8 8 8 8 8 8 8 -1 8 8 8 9 8 -1 8 9 13 8 8 8 9 9 8 9 8 9 8 9 9 8 8 8 8 9 8 8 11 8 8 9 8 8 10 8 8 8 8 8 8 9 8 7 8 8 8 8 -1 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 8 8 8 8 8 8 8 9 8 8 9 8 -1 8 8 8 8 8 8 8 11 8 8 8 8 9 8 8 8 8 -1 -1 8 9 8 8 8 8 12 -1 9 8 8 9 8 11 8 10 8 9 8 9 8 8 8 8 8 8 8 8 ...
result:
ok 200000 lines
Test #40:
score: 30
Accepted
time: 737ms
memory: 230460kb
input:
2000 2000 200000 200000 ............##.##.................#...........#..#.#....#..#....#...#.....#...#....#..#..#....#.##.............###...#.........##..#....##..#.#..#..#.....#........#.............#..#.#.##.#....#..##..#...##......##......#...#...#..#...........................#..#.........#.......
output:
6 6 6 7 6 6 6 7 6 7 7 6 6 6 6 7 6 6 6 6 7 7 7 6 7 6 6 7 7 6 6 6 7 6 6 6 6 6 6 6 7 6 7 7 6 7 6 6 7 7 9 6 6 6 7 7 6 6 7 7 7 6 6 6 7 6 7 9 7 7 7 6 6 6 7 7 7 6 7 8 6 7 6 6 6 6 7 6 8 7 6 6 7 7 6 7 7 6 6 7 6 6 7 6 7 6 8 7 6 7 6 7 7 6 8 7 6 6 7 6 6 6 6 7 7 7 6 7 7 7 7 7 6 7 7 6 7 6 6 6 7 7 6 7 6 7 7 6 6 6 ...
result:
ok 200000 lines
Test #41:
score: 30
Accepted
time: 419ms
memory: 146820kb
input:
2000 2000 20000 200000 ..#.#.....##..##..#..#.......#.#..#...#..#.#.#.....#..#.....#...#.......#......###..#.#.......###.#....#.....#......##.#...........#....#...#.#.#.#...#.#..#...#.....#..##.##.........#.....#.#.........#.##.........#...##.#.###.#.......#.##...#..##.#..#..#.##.#..#..####..#.#.##....
output:
26 25 25 25 28 35 31 25 26 26 -1 23 26 26 26 25 28 29 26 -1 26 26 34 26 26 26 26 28 26 26 23 26 28 26 29 27 26 29 26 26 26 -1 26 25 26 25 26 27 25 26 25 26 35 25 26 -1 26 26 25 26 26 26 25 26 32 23 -1 25 26 27 26 25 25 26 27 26 26 26 28 25 25 24 26 26 25 26 25 26 26 26 27 25 29 26 26 26 29 25 26 26 ...
result:
ok 200000 lines
Test #42:
score: 30
Accepted
time: 283ms
memory: 133256kb
input:
2000 2000 500 2000 #...####....#...#.#.#...#...#..#.##...#..##..#.#######......#..................#.#.............#.....#......#.#..........###.##.#...#.###..####......#..##....###.......#.#......###.###..###.#.....#.##.#..###.########...#...#...###....#####..#############..######.#.#####.########.....
output:
150 150 153 130 154 154 154 146 114 154 150 147 137 155 146 154 154 159 154 146 163 147 147 147 146 154 147 154 147 121 147 146 152 147 163 117 147 142 154 147 122 130 146 146 147 154 154 147 147 154 146 147 146 119 139 170 129 147 146 122 147 147 121 130 147 146 147 137 147 147 132 104 147 177 147 ...
result:
ok 2000 lines
Test #43:
score: 30
Accepted
time: 95ms
memory: 120912kb
input:
2000 2000 500 2000 ............................................................................................................................................................................................................................................................................................
output:
41 1802979 48 44 1802979 31 1802979 1802979 61 1802979 61 48 45 1802979 1802979 61 1802979 61 1802979 1802979 47 1802979 45 1802979 1802979 1802979 1802979 41 1802979 35 61 39 40 48 28 34 1802979 1802979 1802979 60 1802979 33 1802979 60 35 1802979 1802979 1802979 45 41 38 1802979 40 1802979 47 18029...
result:
ok 2000 lines
Test #44:
score: 30
Accepted
time: 569ms
memory: 230812kb
input:
2000 2000 200000 200000 .......................................................................................................................................................................................................................................................................................
output:
133806 133806 133806 4 133806 133806 133806 4 4 4 4 3 133806 4 3 133806 4 4 133806 4 133806 133806 4 133806 133806 4 133806 4 4 4 4 4 4 133806 4 4 4 133806 133806 133806 3 133806 3 133806 133806 4 133806 133806 133806 133806 3 4 4 4 3 133806 4 4 133806 4 3 4 4 3 133806 4 4 4 4 3 133806 133806 133806...
result:
ok 200000 lines
Test #45:
score: 30
Accepted
time: 494ms
memory: 154860kb
input:
2000 2000 200000 200000 .......................................................................................................................................................................................................................................................................................
output:
141 141 141 107 110 141 60 141 110 141 70 107 110 75 141 141 107 110 141 141 141 110 141 141 107 141 141 110 141 105 141 113 141 110 141 110 141 101 141 141 110 110 100 141 80 141 110 141 141 141 94 80 113 110 75 113 85 89 110 141 113 110 141 141 107 141 113 110 141 141 141 110 110 113 80 110 110 14...
result:
ok 200000 lines
Test #46:
score: 30
Accepted
time: 653ms
memory: 220884kb
input:
2000 2000 200000 200000 .......................................................................................................................................................................................................................................................................................
output:
97 84 97 97 97 97 84 97 97 97 71 84 84 97 97 97 90 58 97 72 84 78 84 97 76 97 97 74 97 83 84 97 72 90 84 97 97 97 76 97 69 84 6 97 97 97 97 97 76 90 97 97 84 97 97 97 76 72 97 97 6 97 97 90 7 90 76 97 97 97 97 7 97 58 97 78 76 97 97 97 84 83 76 72 84 97 97 97 97 84 97 84 97 71 97 83 84 6 90 7 84 6 9...
result:
ok 200000 lines
Test #47:
score: 30
Accepted
time: 565ms
memory: 185552kb
input:
2000 2000 200000 200000 .......................................................................................................................................................................................................................................................................................
output:
70 70 83 83 73 76 83 40 83 83 83 83 73 74 83 83 73 72 67 46 76 72 73 73 79 74 61 73 54 73 75 75 74 83 66 73 75 75 73 73 83 76 74 76 76 76 75 83 79 73 76 83 83 75 74 83 76 74 70 70 55 83 75 74 83 75 76 73 76 83 67 83 83 83 73 56 83 83 76 83 73 83 66 73 83 8 69 83 74 73 64 76 75 75 83 74 73 83 83 73 7...
result:
ok 200000 lines
Extra Test:
score: 0
Extra Test Passed