QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736977#5135. Kiosk ConstructionNegationistTL 95ms3860kbC++202.4kb2024-11-12 14:08:252024-11-12 14:08:27

Judging History

你现在查看的是最新测评结果

  • [2024-11-12 14:08:27]
  • 评测
  • 测评结果:TL
  • 用时:95ms
  • 内存:3860kb
  • [2024-11-12 14:08:25]
  • 提交

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...

output:


result: