QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203465 | #2474. Art Transaction | nameless_story# | WA | 0ms | 3916kb | C++20 | 7.5kb | 2023-10-06 17:39:12 | 2023-10-06 17:39:12 |
Judging History
answer
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
const int dbg=0;
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
cout<<fixed<<setprecision(15);
int n,i,j,k,l;
cin>>n;
{
string ip;
getline(cin,ip);
}
vector<string> a(n);
for (auto &s:a)
{
getline(cin,s);
s.resize(n,' ');
// cerr<<s<<endl;
}
auto av=[&](int x,int y) { return x>=0&&y>=0&&x<n&&y<n; };
ll ans=0;
{//suns
int cnt=0;
const static int dx[8]={1,1,1,0,0,-1,-1,-1};
const static int dy[8]={-1,0,1,-1,1,-1,0,1};
vector ed(n,vector<int>(n));
for (i=0; i<n; i++) for (j=0; j<n; j++) if (a[i][j]=='*') for (l=0; l<8; l++) for (k=1; k<n; k++)
{
int x=i+dx[l]*k,y=j+dy[l]*k;
if (!av(x,y)) break;
if (a[x][y]==' ') continue;
ed[x][y]=1;
break;
}
for (i=0; i<n; i++) for (j=0; j<n; j++) if (a[i][j]!='*'&&ed[i][j])
++cnt;
ans+=cnt*100;
if (dbg) cerr<<"suns: "<<cnt<<' '<<ans<<endl;
}
{//biggest bird
int cnt=0;
const static int dx[4]={0,1,-1,0};
const static int dy[4]={1,0,0,-1};
vector ed(n,vector<int>(n));
for (i=0; i<n; i++) for (j=0; j<n; j++) if (!ed[i][j]&&(a[i][j]=='D'||a[i][j]=='v'))
{
vector<pair<int,int>> axis;
function<void(int,int)> dfs=[&](int x,int y)
{
ed[x][y]=1;
axis.push_back({x,y});
for (int k=0; k<4; k++) if (int nx=x+dx[k],ny=y+dy[k]; av(nx,ny)&&!ed[nx][ny]&&(a[nx][ny]=='D'||a[nx][ny]=='v')) dfs(nx,ny);
};
dfs(i,j);
for (auto &[x,y]:axis) swap(x,y);
sort(all(axis));
map<pair<int,int>,int> dp;
int mx=0;
for (auto [x,y]:axis) cmax(mx,dp[{x,y}]=dp[{x-1,y}]+1);
cnt+=mx;
}
ans+=cnt*500;
if (dbg) cerr<<"biggest bird: "<<cnt<<' '<<ans<<endl;
}
{//Flock perimeter
int cnt=0;
const static int dx[4]={0,1,-1,0};
const static int dy[4]={1,0,0,-1};
vector ed(n,vector<int>(n));
for (i=0; i<n; i++) for (j=0; j<n; j++) if (!ed[i][j]&&(a[i][j]=='D'||a[i][j]=='v'))
{
int cur=0;
function<void(int,int)> dfs=[&](int x,int y)
{
ed[x][y]=1;
for (int k=0; k<4; k++) if (int nx=x+dx[k],ny=y+dy[k]; av(nx,ny)&&!ed[nx][ny]&&(a[nx][ny]=='D'||a[nx][ny]=='v')) dfs(nx,ny);
else if (!av(nx,ny)||a[nx][ny]!='D'&&a[nx][ny]!='v')
{
++cur;
}
};
dfs(i,j);
cnt+=cur;
}
ans+=cnt*60;
if (dbg) cerr<<"Flock perimeter: "<<cnt<<' '<<ans<<endl;
}
{//House view up
int cnt=0;
for (i=0; i<n; i++) for (j=0; j<n; j++) if (a[i][j]==' ')
{
for (k=i+1; k<n; k++) if (a[k][j]!=' ')
{
cnt+=a[k][j]=='^';
break;
}
}
ans+=cnt*10;
if (dbg) cerr<<"House view up: "<<cnt<<' '<<ans<<endl;
}
{//3*3 blocks
set<string> s;
for (i=0; i+2<n; i++) for (j=0; j+2<n; j++) s.insert(a[i].substr(j,3)+a[i+1].substr(j,3)+a[i+2].substr(j,3));
int cnt=s.size();
if (dbg) cerr<<"3*3 blocks: "<<cnt<<' '<<ans<<endl;
ans+=1*cnt;
}
{//Animals 1
int cnt=0;
const static int dx[4]={0,1,-1,0};
const static int dy[4]={1,0,0,-1};
for (i=0; i<n; i++) for (j=0; j<n; j++) if (a[i][j]=='!'||a[i][j]=='D'||a[i][j]=='v')
for (k=0; k<4; k++)
{
int x=i+dx[k],y=j+dy[k];
// cerr<<i<<' '<<j<<' '<<x<<' '<<y<<endl;
cnt+=av(x,y)&&a[x][y]==' ';
}
ans+=cnt*15;
if (dbg) cerr<<"Animals 1: "<<cnt<<' '<<ans<<endl;
}
{//Freedom
const static int dx[4]={0,1,-1,0};
const static int dy[4]={1,0,0,-1};
vector ed(n,vector<int>(n));
function<void(int,int)> dfs=[&](int x,int y)
{
if (!av(x,y)||ed[x][y]) return;
ed[x][y]=1;
if (a[x][y]!=' ') return;
for (int k=0; k<4; k++) dfs(x+dx[k],y+dy[k]);
};
for (i=0; i<n; i++)
{
dfs(i,0); dfs(0,i);
dfs(i,n-1); dfs(n-1,i);
}
int cnt=0;
for (i=0; i<n; i++) for (j=0; j<n; j++) cnt+=ed[i][j]&&a[i][j]!=' ';
ans+=cnt*7;
if (dbg) cerr<<"Freedom: "<<cnt<<' '<<ans<<endl;
}
{//Chupacabra
const static int dx[8]={1,-1,1,-1,2,2,-2,-2};
const static int dy[8]={2,2,-2,-2,1,-1,1,-1};
vector ed(n,vector<int>(n));
for (i=0; i<n; i++) for (j=0; j<n; j++) if (a[i][j]=='!') for (l=0; l<8; l++)
{
int x=i+dx[l],y=j+dy[l];
if (!av(x,y)) continue;
ed[x][y]=1;
}
int cnt=0;
for (i=0; i<n; i++) for (j=0; j<n; j++)
cnt+=(a[i][j]=='D'||a[i][j]=='v')&&ed[i][j];
ans+=cnt*200;
if (dbg) cerr<<"Chupacabra: "<<cnt<<' '<<ans<<endl;
}
{//Peaks
ll cnt=0;
vector<pair<int,int>> peak;
for (i=0; i<n; i++) for (j=0; j+1<n; j++) if (a[i].substr(j,2)=="/\\")
peak.push_back({i,j});
for (auto [x1,y1]:peak)
{
int mx=0;
for (auto [x2,y2]:peak) cmax(mx,abs(x1-x2)+abs(y1-y2));
cnt+=mx;
}
ans+=cnt*50;
if (dbg) cerr<<"Peaks: "<<cnt<<' '<<ans<<endl;
}
{//Drake/grill
int cnt=0;
const static int dx[4]={0,1,-1,0};
const static int dy[4]={1,0,0,-1};
for (i=0; i<n; i++) for (j=0; j<n; j++) if (a[i][j]=='D') for (k=0; k<4; k++)
{
int x=i+dx[k],y=j+dy[k];
if (av(x,y)&&a[x][y]=='G')
{
++cnt;
break;
}
}
ans+=cnt*500;
if (dbg) cerr<<"Drake/grill: "<<cnt<<' '<<ans<<endl;
}
{//Minimum frequency
vector<int> cnt(256);
for (auto &v:a) for (char c:v) ++cnt[c];
vector<int> mns;
for (char c:"*^!/\\vDG"s) if (cnt[c]) mns.push_back(cnt[c]);
int mn=*min_element(all(mns));
ll cc=0;
for (ll x:mns) if (x==mn) cc+=x;
ans+=cc*10;
if (dbg) cerr<<"Minimum frequency: "<<cc<<' '<<ans<<endl;
}
{//Empty fields
int cnt=0;
for (auto &v:a) cnt+=count(all(v),' ');
ans+=cnt*1;
if (dbg) cerr<<"Empty fields: "<<cnt<<' '<<ans<<endl;
}
{//Animals 2
vector<int> cnt(256);
for (auto &v:a) for (char c:v) ++cnt[c];
int cc=cnt['!']*cnt['v']*cnt['D'];
ans+=1*cc;
if (dbg) cerr<<"Animals 2: "<<cc<<' '<<ans<<endl;
}
{//House view down
int cnt=0;
for (i=0; i<n; i++) for (j=0; j<n; j++) if (a[i][j]==' ')
{
for (k=i-1; k>=0; k--) if (a[k][j]!=' ')
{
cnt+=a[k][j]=='^';
break;
}
}
ans+=cnt*5;
if (dbg) cerr<<"House view down: "<<cnt<<' '<<ans<<endl;
}
{//Drake/grill
int cnt=0;
const static int dx[4]={0,1,-1,0};
const static int dy[4]={1,0,0,-1};
for (i=0; i<n; i++) for (j=0; j<n; j++) if (a[i][j]=='G') for (k=0; k<4; k++)
{
int x=i+dx[k],y=j+dy[k];
if (av(x,y)&&a[x][y]=='D')
{
++cnt;
break;
}
}
ans+=cnt*50;
if (dbg) cerr<<"Drake/grill: "<<cnt<<' '<<ans<<endl;
}
{//Houses and grills
int cc=0;
vector<int> cnt(256);
for (auto &v:a) for (char c:v) ++cnt[c];
cc=min(cnt['^'],cnt['G']);
ans+=3*cc;
if (dbg) cerr<<"Houses and grills: "<<cc<<' '<<ans<<endl;
}
//sun *
//house ^
//chupacabra !
//left slope /
//right slope \
//bird v
//drake D
//grill G
cout<<ans<<endl;
}
/*
suns: 9 900
biggest bird: 2 1900
Flock perimeter: 22 3220
House view up: 0 3220
Animals 1: 0 3269
Freedom: 30 3479
Chupacabra: 0 3479
Peaks: 56 6279
Drake/grill: 9 10779
Minimum frequency: 72 11499
Empty fields: 9 11508
Animals 2: 729 12237
House view down: 0 12237
Drake/grill: 9 12687
Houses and grills: 9 12714
suns: 0 0
biggest bird: 2 1000
Flock perimeter: 8 1480
House view up: 0 1480
Animals 1: 8 1601
Freedom: 3 1622
Chupacabra: 2 2022
Peaks: 0 2022
Drake/grill: 0 2022
Minimum frequency: 0 2022
Empty fields: 6 2028
Animals 2: 1 2029
House view down: 0 2029
Drake/grill: 0 2029
Houses and grills: 0 2029
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3916kb
input:
2 / ^G
output:
65
result:
wrong answer 1st lines differ - expected: '70', found: '65'