QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#355590 | #5112. Where Am I? | InfinityNS# | WA | 486ms | 9524kb | C++14 | 3.6kb | 2024-03-16 21:55:59 | 2024-03-16 21:56:00 |
Judging History
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]);
}
return min(size(),p.size());
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4268kb
input:
1 1 X
output:
0.0000000000 0 (1,1)
result:
ok correct!
Test #2:
score: 0
Accepted
time: 1ms
memory: 4196kb
input:
2 1 .X
output:
0.0000000000 0 (1,1) (2,1)
result:
ok correct!
Test #3:
score: 0
Accepted
time: 1ms
memory: 4200kb
input:
2 1 X.
output:
0.0000000000 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 4436kb
input:
1 2 . X
output:
0.0000000000 0 (1,1) (1,2)
result:
ok correct!
Test #5:
score: 0
Accepted
time: 1ms
memory: 4424kb
input:
1 2 X .
output:
0.0000000000 0 (1,1) (1,2)
result:
ok correct!
Test #6:
score: 0
Accepted
time: 0ms
memory: 4212kb
input:
2 1 XX
output:
3.0000000000 3 (1,1) (2,1)
result:
ok correct!
Test #7:
score: 0
Accepted
time: 0ms
memory: 4208kb
input:
3 3 XXX X.X XXX
output:
3.1111111111 5 (3,1) (3,2)
result:
ok correct!
Test #8:
score: 0
Accepted
time: 485ms
memory: 9524kb
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: 473ms
memory: 4700kb
input:
100 100 X................................................................................................... .................................................................................................... .............................................................................................
output:
19735.3199000000 39599 (100,1) (100,2)
result:
ok correct!
Test #10:
score: 0
Accepted
time: 467ms
memory: 4776kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
19865.6699000000 39500 (100,1) (100,2)
result:
ok correct!
Test #11:
score: -100
Wrong Answer
time: 486ms
memory: 9484kb
input:
100 100 X................................................................................................... .X.................................................................................................. ..X..........................................................................................
output:
11855.6392000000 39302 (99,100) (100,99)
result:
wrong answer Read (99,100) but expected (100,99)