QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736926#5135. Kiosk ConstructionNegationistWA 0ms3568kbC++201.9kb2024-11-12 13:58:182024-11-12 13:58:18

Judging History

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

  • [2024-11-12 13:58:18]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3568kb
  • [2024-11-12 13:58:18]
  • 提交

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(j>1){
        if(abs(a[i][j-1]-goal)<best){
            best = abs(a[i][j-1]-goal);
            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};
        }
    }
    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: 3568kb

input:

2 3
1 2 3
6 5 4

output:

2 2

result:

ok 

Test #2:

score: 0
Accepted
time: 0ms
memory: 3464kb

input:

3 3
1 4 8
7 5 2
3 9 6

output:

impossible

result:

ok 

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3504kb

input:

3 3
9 3 1
4 7 2
8 6 5

output:

3 3

result:

FAIL Reported distance does not equal actual distance.