QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#736977 | #5135. Kiosk Construction | Negationist | TL | 95ms | 3860kb | C++20 | 2.4kb | 2024-11-12 14:08:25 | 2024-11-12 14:08:27 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pair<int,int>>
using namespace std;
int h, w;
int get2(int i, int j, vector<vi>&a, int goal, int cnt){
if(a[i][j]==goal){
return cnt;
}
if(cnt>2*h*w){
return LLONG_MAX;
}
pii next = {-1,-1};
int best = LLONG_MAX;
if(i>1){
if(abs(a[i-1][j]-goal)<best){
best = abs(a[i-1][j]-goal);
next = {i-1,j};
}
}
if(i<h){
if(abs(a[i+1][j]-goal)<best){
best = abs(a[i+1][j]-goal);
next = {i+1,j};
}
if(abs(a[i+1][j]-goal)==best){
if(abs(a[i+1][j]-a[i][j]) < abs(a[i][j]-a[next.ff][next.ss])){
next = {i+1,j};
}
}
}
if(j>1){
if(abs(a[i][j-1]-goal)<best){
best = abs(a[i][j-1]-goal);
next = {i,j-1};
}
if(abs(a[i][j-1]-goal)==best){
if(abs(a[i][j-1]-a[i][j]) < abs(a[i][j]-a[next.ff][next.ss])){
next = {i,j-1};
}
}
}
if(j<w){
if(abs(a[i][j+1]-goal)<best){
best = abs(a[i][j+1]-goal);
next = {i,j+1};
}
if(abs(a[i][j+1]-goal)==best){
if(abs(a[i][j+1]-a[i][j]) < abs(a[i][j+1]-a[next.ff][next.ss])){
next = {i,j+1};
}
}
}
return get2(next.ff,next.ss,a, goal, cnt+1);
}
int get(vector<vi>&a, int x, int y){
int ans = -1;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
int res = get2(x,y,a,a[i][j],0);
ans = max(ans,res);
}
}
return ans;
}
void solve(){
cin >> h >> w;
vector<vi> a(h+1,vector<int> (w+1));
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
cin >> a[i][j];
}
}
pii ans = {-1,LLONG_MAX};
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
int res = get(a,i,j);
if(res<ans.ss){
ans = {a[i][j],res};
}
}
}
if(ans.ss==LLONG_MAX){
cout << "impossible\n";
return;
}
cout << ans.ff << " " << ans.ss << "\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3500kb
input:
2 3 1 2 3 6 5 4
output:
2 2
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 3 1 4 8 7 5 2 3 9 6
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 3 9 3 1 4 7 2 8 6 5
output:
4 3
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
2 2 1 2 3 4
output:
1 2
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
2 2 4 3 1 2
output:
4 2
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 3 3 5 2 6 1 4
output:
impossible
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
2 3 5 3 4 1 6 2
output:
6 2
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 2 2 4 6 3 1 5
output:
6 2
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
3 3 1 5 9 7 2 8 6 4 3
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
3 3 8 3 9 5 6 2 1 4 7
output:
impossible
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
5 3 4 12 8 7 6 10 2 1 13 3 9 14 5 11 15
output:
impossible
result:
ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
5 5 24 23 3 10 1 6 7 9 18 5 25 2 20 11 8 4 13 12 14 15 17 21 22 19 16
output:
impossible
result:
ok
Test #13:
score: 0
Accepted
time: 12ms
memory: 3852kb
input:
10 10 83 24 7 98 40 18 56 81 12 73 77 87 33 22 61 38 8 48 63 34 25 29 72 97 28 26 54 3 89 13 65 60 42 45 55 36 16 70 17 5 90 69 74 64 99 31 9 2 66 51 44 35 14 58 71 27 92 84 32 100 6 82 37 76 52 43 39 59 91 41 50 11 15 85 62 10 20 86 53 95 46 68 4 49 1 75 93 19 23 57 80 96 78 67 79 30 88 47 94 21
output:
impossible
result:
ok
Test #14:
score: 0
Accepted
time: 95ms
memory: 3860kb
input:
20 10 86 175 137 160 149 72 135 64 2 131 134 83 66 148 141 1 171 90 178 57 108 152 179 136 47 67 142 124 121 59 146 41 126 89 114 118 196 112 125 19 26 180 50 107 96 188 128 14 94 88 156 7 49 76 91 117 56 104 161 127 105 195 184 40 24 139 3 190 106 80 116 21 34 12 87 97 130 140 103 98 192 81 157 194...
output:
impossible
result:
ok
Test #15:
score: 0
Accepted
time: 3ms
memory: 3560kb
input:
2 40 59 36 73 43 16 15 2 49 51 21 30 79 60 78 48 19 4 45 77 65 3 63 22 11 57 58 54 76 27 70 25 12 62 69 29 1 50 35 14 17 71 56 13 66 75 26 6 68 37 72 46 38 53 8 41 24 32 31 33 80 23 64 5 52 20 9 40 61 34 10 39 47 67 74 42 18 7 55 28 44
output:
impossible
result:
ok
Test #16:
score: -100
Time Limit Exceeded
input:
40 40 1545 1478 236 1013 790 988 319 1231 822 1598 1505 529 340 1441 224 681 1449 537 151 1087 966 552 938 101 676 136 807 1507 1079 328 1200 34 645 1127 316 518 357 726 121 1314 971 1266 564 954 468 627 1198 208 799 793 956 1206 70 343 406 221 142 408 1131 1533 504 1279 764 629 498 455 366 1407 991...