QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#355595#5112. Where Am I?InfinityNS#WA 496ms9624kbC++143.7kb2024-03-16 22:08:062024-03-16 22:08:06

Judging History

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

  • [2024-03-16 22:08:06]
  • 评测
  • 测评结果:WA
  • 用时:496ms
  • 内存:9624kb
  • [2024-03-16 22:08:06]
  • 提交

answer

#include<bits/stdc++.h>
#define ff first
#define pb push_back
#define ss second

using namespace std;
typedef pair<int,int> pii;

struct pt{
    int x,y;

    pt(){}
    pt(int x,int y){
        this->x=x;
        this->y=y;
    }

    pt operator +(pt b){
        return pt(x+b.x,y+b.y);
    }
    pt operator -(pt b){
        return pt(x-b.x,y-b.y);
    }

    void ispis(){
        printf("%d %d PT\n",x,y);
    }

};

const int maxn=210;
const int maxlen=maxn*maxn;
///const int maxlen=20;
int n,m,a[maxn][maxn];
pt shift[maxlen];
pt dir[4]={ pt(0,1) ,pt(1,0) ,pt(0,-1) ,pt(-1,0)};

void prek(){

    int cnt=0;
    int clen=1;
    int cntlen=0;
    int cdir=0;
    for(int i=1;i<maxlen;i++){

        shift[i]=shift[i-1]+dir[cdir];

        cntlen++;
        if(cntlen==clen){
            cnt++;
            cntlen=0;
            cdir=(cdir+1)%4;
        }

        if(cnt==2){
            cnt=0;
            clen++;
        }

        ///shift[i].ispis();
    }

}

struct path{

    pt c;
    vector<int>a;

    path(pt c){
        this->c=c;
    }

    void pb(int x){
        a.pb(x);
    }
    int size() const{
        return a.size();
    }
    int operator [](int x) const{
        return a[x];
    }

    bool operator <(const path &p)const{

        int sz=min(size(),p.size());
        for(int i=0;i<sz;i++){
            if(a[i]==p[i])continue;
            return a[i]<p[i];
        }
        return size()<p.size();
    }

    int break_position(const path &p)const{

        int sz=min(size(),p.size());
        for(int i=0;i<sz;i++){
            if(a[i]==p[i])continue;
            return min(a[i],p[i]);
        }
        int pos=sz;
        if(pos<p.size())return p[pos];
        else return a[pos];
    }

    void ispis(){

        printf("%d %d | ",c.x,c.y);
        for(int i=0;i<a.size();i++){
            printf("%d ",a[i]);
        }
        printf(" PATH\n");

    }

};

vector<path>paths;
int steps[maxn][maxn];

path get_path(pt p){

    pt curr;
    path ret(p);
    for(int i=0;i<maxlen;i++){
        pt curr=p+shift[i];
        if(curr.x>m || curr.x<1 || curr.y<1 || curr.y>n)continue;
        if(a[curr.x][curr.y])ret.pb(i);
    }
    return ret;
}

int main(){

    ///freopen("test.txt","r",stdin);

    prek();

    scanf("%d %d",&m,&n);

    for(int i=n;i>=1;i--){
        string s;
        cin>>s;
        for(int j=1;j<=m;j++){
            if(s[j-1]=='.')a[j][i]=0;
            else a[j][i]=1;
        }

    }

    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            paths.pb(get_path(pt(j,i)));

           // paths.back().ispis();
        }
    }

    sort(paths.begin(),paths.end());

    for(int i=0;i<paths.size();i++){

        int pom=0;
        if(i>0){
            pom=max(pom,paths[i].break_position(paths[i-1]));
        }
        if(i<paths.size()-1){
            pom=max(pom,paths[i].break_position(paths[i+1]));
        }

        steps[paths[i].c.x][paths[i].c.y]=pom;

    }

    double rez=0;
    int mx=0;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            rez+=steps[j][i];
            //printf("%d ",steps[j][i]);
            mx=max(mx,steps[j][i]);
        }
        //printf("\n");
    }

    vector<pii>retz;
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            if(steps[j][i]==mx)retz.pb({j,i});
        }
    }

    cout<<fixed<<setprecision(10)<<rez/(n*m)<<endl;
    sort(retz.begin(),retz.end());
    cout<<mx<<endl;
    for(int i=0;i<retz.size();i++){
        printf("(%d,%d) ",retz[i].ff,retz[i].ss);
    }
    printf("\n");

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4304kb

input:

1 1
X

output:

0.0000000000
0
(1,1) 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 1ms
memory: 4284kb

input:

2 1
.X

output:

0.0000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.0000000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.0000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

score: 0
Accepted
time: 1ms
memory: 4272kb

input:

1 2
X
.

output:

0.0000000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

score: 0
Accepted
time: 1ms
memory: 4208kb

input:

2 1
XX

output:

3.0000000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

score: 0
Accepted
time: 1ms
memory: 4304kb

input:

3 3
XXX
X.X
XXX

output:

3.1111111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 473ms
memory: 9624kb

input:

100 100
..X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X..
....................................................................................................
X............................................................................................

output:

4757.9471000000
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 477ms
memory: 4872kb

input:

100 100
X...................................................................................................
....................................................................................................
.............................................................................................

output:

19735.3199000000
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 486ms
memory: 4708kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19865.6699000000
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: -100
Wrong Answer
time: 496ms
memory: 9536kb

input:

100 100
X...................................................................................................
.X..................................................................................................
..X..........................................................................................

output:

11855.6392000000
39302
(99,100) (100,99) 

result:

wrong answer Read (99,100) but expected (100,99)