QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69641#5112. Where Am I?ricky0129WA 449ms7592kbC++142.8kb2022-12-29 05:45:572022-12-29 05:45:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-29 05:45:58]
  • 评测
  • 测评结果:WA
  • 用时:449ms
  • 内存:7592kb
  • [2022-12-29 05:45:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define FOR(i,n) for(int i=0;i<n;i++)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second

const int MOD = (int)1e9+7;

int r,c;
int cc = 0;
//char G[100][100];
vector<string> G;
bool inside(int i, int j){
    return (i>=0 && i<r && j>=0 && j<c);
}
void turn(pii& dir){
    dir = make_pair(dir.s,-dir.f);
}
vector<int> simulate(int i, int j){
    vector<int> pos; 
    int seen = 0;
    int times = 1;
    int tt = 0;
    int curr = 0;
    pii dir = make_pair(-1,0);
    if(G[i][j]=='X'){
        seen++;
        pos.pb(0);
    }
    int kk = 0;
    while(seen!=cc){
        i+=dir.f; j+=dir.s;
        kk++;
        if(inside(i,j) && G[i][j]=='X'){
            pos.pb(kk);
            seen++;
        }
        curr++;
        if(curr==times){
            turn(dir);
            curr = 0; 
            tt++;
            if(tt==2){
                tt = 0; 
                times++;
            }
        }
    }
    return pos;
}
struct info{
    vi arr;
    pii pos;
    info(){}
    info(vi& a, pii start){
        arr = a; 
        pos = start;
    }
    bool operator< (const info& lhs) const { return arr < lhs.arr; } 
};
int main()
{
    //scanf("%d %d\n",&c,&r);
    cin>>c>>r;
    /*
    FOR(i,r) FOR(j,c){
        scanf("%c",&G[i][j]);
        if(G[i][j]=='X') cc++;

    }
    */
    G.resize(r);
    FOR(i,r) cin>>G[i];
    FOR(i,r) FOR(j,c) if(G[i][j]=='X') cc++;
    vector<info> A;
    FOR(i,r){
        FOR(j,c){
            //simulate until you reach all X's
            vi all = simulate(i,j);
            A.pb(info(all,make_pair(i,j)) );
        }
    }
    sort(A.begin(),A.end());
    int ans = 0;
    ll sum = 0;
    vi ans_m(sz(A),0);
    for(int i=0;i<sz(A)-1;i++){
        int l = sz(A[i].arr);
        int r = sz(A[i+1].arr);
        FOR(j,min(l,r)){
            if(A[i].arr[j]!=A[i+1].arr[j]){
                int val = min(A[i].arr[j],A[i+1].arr[j]);
                ans_m[i] = max(ans_m[i],val);
                ans_m[i+1] = max(ans_m[i+1],val);
                ans = max(ans,val);
                break;
            }
        }
    }
    FOR(i,sz(A)) sum+=ans_m[i];
    double ex = sum/(double)sz(A);
    printf("%.8lf\n%d\n",ex,ans);
    vector<pii> all;
    FOR(i,sz(A)) if(ans_m[i]==ans){
        all.pb(make_pair(A[i].pos.s+1,r-A[i].pos.f));
    }
    sort(all.begin(),all.end());
    FOR(i,sz(all)) printf("(%d,%d) ",all[i].f,all[i].s);
    printf("\n");
    //cout<<ex<<endl;
    //cout<<ans<<endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3744kb

input:

1 1
X

output:

0.00000000
0
(1,1) 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 2ms
memory: 3692kb

input:

2 1
.X

output:

0.00000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

score: 0
Accepted
time: 3ms
memory: 3700kb

input:

2 1
X.

output:

0.00000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

1 2
.
X

output:

0.00000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.00000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.00000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

3 3
XXX
X.X
XXX

output:

3.11111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 442ms
memory: 7084kb

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.94710000
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 309ms
memory: 4152kb

input:

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

output:

19735.31990000
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 314ms
memory: 3860kb

input:

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

output:

19865.66990000
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: -100
Wrong Answer
time: 449ms
memory: 7592kb

input:

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

output:

11855.63920000
39302
(99,100) (100,99) 

result:

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