QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203465#2474. Art Transactionnameless_story#WA 0ms3916kbC++207.5kb2023-10-06 17:39:122023-10-06 17:39:12

Judging History

This is the latest submission verdict.

  • [2023-10-06 17:39:12]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3916kb
  • [2023-10-06 17:39:12]
  • Submitted

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'