QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#17938#2213. KnightCharlieVinnie#AC ✓471ms99308kbC++141.4kb2022-01-15 13:33:082022-05-04 16:29:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 16:29:06]
  • 评测
  • 测评结果:AC
  • 用时:471ms
  • 内存:99308kb
  • [2022-01-15 13:33:08]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define clr(a,v) memset(a,v,sizeof(a))
#define Freopen(file) \
freopen(file".in","r",stdin); \
freopen(file".out","w",stdout);
//#define int long long
using namespace std;

const int N=1e3+5;

char mp[N][N];
int n,m,r,c;
int num[N][N],ncnt;
vector<int> to[N*N];
int col[N*N];

void add(int x,int y)
{
	to[x].push_back(y);
}

void dfs(int u,int cc)
{
	col[u]=cc;
	
	for(auto v:to[u]){
		if(col[v]){
			assert(col[v]==3-cc);
			continue;
		}
		dfs(v,3-cc);
	}
}

bool valid(int x,int y)
{
	return x>=1 && x<=n && y>=1 && y<=m && mp[x][y]!='@';
}

signed main()
{
	cin>>n>>m>>r>>c;
	For(i,1,n) cin>>(mp[i]+1);
	
	if(r==0&&c==0){
		puts("Bob");
		return 0;
	}
	
	int S=0,T=0;
	
	For(i,1,n){
		For(j,1,m){
			if(mp[i][j]!='@') num[i][j]=++ncnt;
			if(mp[i][j]=='A') S=ncnt;
			if(mp[i][j]=='B') T=ncnt;
		}
	}
	
	For(i,1,n){
		For(j,1,m){
			if(mp[i][j]!='@'){
				for(int x=-1;x<=1;x+=2){
					for(int y=-1;y<=1;y+=2){
						if(valid(i+x*r,j+y*c)) add(num[i][j],num[i+x*r][j+y*c]);
						if(valid(i+x*c,j+y*r)) add(num[i][j],num[i+x*c][j+y*r]);
					}
				}
			}
		}
	}
	
	if(to[S].empty()){
		puts("Bob");
		return 0;
	}
	
	dfs(S,1);
	
	if(col[T]==0){
		puts("Alice");
	}
	else{
		if(col[T]==col[S]){
			puts("Alice");
		}
		else{
			puts("Bob");
		}
	}
	
	return 0;
}

Details

Test #1:

score: 100
Accepted
time: 51ms
memory: 45664kb

Test #2:

score: 0
Accepted
time: 4ms
memory: 29744kb

Test #3:

score: 0
Accepted
time: 119ms
memory: 53140kb

Test #4:

score: 0
Accepted
time: 61ms
memory: 41968kb

Test #5:

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

Test #6:

score: 0
Accepted
time: 20ms
memory: 33604kb

Test #7:

score: 0
Accepted
time: 4ms
memory: 29140kb

Test #8:

score: 0
Accepted
time: 5ms
memory: 30376kb

Test #9:

score: 0
Accepted
time: 38ms
memory: 41728kb

Test #10:

score: 0
Accepted
time: 17ms
memory: 33304kb

Test #11:

score: 0
Accepted
time: 13ms
memory: 33352kb

Test #12:

score: 0
Accepted
time: 60ms
memory: 50304kb

Test #13:

score: 0
Accepted
time: 23ms
memory: 34076kb

Test #14:

score: 0
Accepted
time: 42ms
memory: 42952kb

Test #15:

score: 0
Accepted
time: 4ms
memory: 32664kb

Test #16:

score: 0
Accepted
time: 18ms
memory: 32920kb

Test #17:

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

Test #18:

score: 0
Accepted
time: 9ms
memory: 33136kb

Test #19:

score: 0
Accepted
time: 6ms
memory: 30076kb

Test #20:

score: 0
Accepted
time: 44ms
memory: 39256kb

Test #21:

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

Test #22:

score: 0
Accepted
time: 5ms
memory: 30948kb

Test #23:

score: 0
Accepted
time: 4ms
memory: 29000kb

Test #24:

score: 0
Accepted
time: 15ms
memory: 32768kb

Test #25:

score: 0
Accepted
time: 8ms
memory: 33928kb

Test #26:

score: 0
Accepted
time: 4ms
memory: 29768kb

Test #27:

score: 0
Accepted
time: 5ms
memory: 28160kb

Test #28:

score: 0
Accepted
time: 105ms
memory: 54240kb

Test #29:

score: 0
Accepted
time: 8ms
memory: 29956kb

Test #30:

score: 0
Accepted
time: 13ms
memory: 33412kb

Test #31:

score: 0
Accepted
time: 23ms
memory: 32088kb

Test #32:

score: 0
Accepted
time: 5ms
memory: 29492kb

Test #33:

score: 0
Accepted
time: 93ms
memory: 49360kb

Test #34:

score: 0
Accepted
time: 7ms
memory: 32660kb

Test #35:

score: 0
Accepted
time: 82ms
memory: 47412kb

Test #36:

score: 0
Accepted
time: 105ms
memory: 49600kb

Test #37:

score: 0
Accepted
time: 7ms
memory: 30956kb

Test #38:

score: 0
Accepted
time: 29ms
memory: 34196kb

Test #39:

score: 0
Accepted
time: 5ms
memory: 30040kb

Test #40:

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

Test #41:

score: 0
Accepted
time: 26ms
memory: 35336kb

Test #42:

score: 0
Accepted
time: 20ms
memory: 33524kb

Test #43:

score: 0
Accepted
time: 37ms
memory: 35916kb

Test #44:

score: 0
Accepted
time: 8ms
memory: 29416kb

Test #45:

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

Test #46:

score: 0
Accepted
time: 4ms
memory: 31056kb

Test #47:

score: 0
Accepted
time: 8ms
memory: 30660kb

Test #48:

score: 0
Accepted
time: 91ms
memory: 47012kb

Test #49:

score: 0
Accepted
time: 44ms
memory: 41608kb

Test #50:

score: 0
Accepted
time: 14ms
memory: 33412kb

Test #51:

score: 0
Accepted
time: 219ms
memory: 66088kb

Test #52:

score: 0
Accepted
time: 169ms
memory: 66192kb

Test #53:

score: 0
Accepted
time: 40ms
memory: 38728kb

Test #54:

score: 0
Accepted
time: 282ms
memory: 85376kb

Test #55:

score: 0
Accepted
time: 117ms
memory: 51288kb

Test #56:

score: 0
Accepted
time: 349ms
memory: 83164kb

Test #57:

score: 0
Accepted
time: 135ms
memory: 51284kb

Test #58:

score: 0
Accepted
time: 37ms
memory: 35912kb

Test #59:

score: 0
Accepted
time: 60ms
memory: 37712kb

Test #60:

score: 0
Accepted
time: 374ms
memory: 86708kb

Test #61:

score: 0
Accepted
time: 90ms
memory: 48892kb

Test #62:

score: 0
Accepted
time: 72ms
memory: 43396kb

Test #63:

score: 0
Accepted
time: 295ms
memory: 68924kb

Test #64:

score: 0
Accepted
time: 49ms
memory: 37900kb

Test #65:

score: 0
Accepted
time: 181ms
memory: 78384kb

Test #66:

score: 0
Accepted
time: 36ms
memory: 37756kb

Test #67:

score: 0
Accepted
time: 129ms
memory: 56176kb

Test #68:

score: 0
Accepted
time: 58ms
memory: 40116kb

Test #69:

score: 0
Accepted
time: 353ms
memory: 90444kb

Test #70:

score: 0
Accepted
time: 93ms
memory: 45128kb

Test #71:

score: 0
Accepted
time: 77ms
memory: 47036kb

Test #72:

score: 0
Accepted
time: 38ms
memory: 35992kb

Test #73:

score: 0
Accepted
time: 60ms
memory: 50544kb

Test #74:

score: 0
Accepted
time: 395ms
memory: 83928kb

Test #75:

score: 0
Accepted
time: 115ms
memory: 53600kb

Test #76:

score: 0
Accepted
time: 116ms
memory: 55688kb

Test #77:

score: 0
Accepted
time: 296ms
memory: 74732kb

Test #78:

score: 0
Accepted
time: 28ms
memory: 36872kb

Test #79:

score: 0
Accepted
time: 65ms
memory: 43268kb

Test #80:

score: 0
Accepted
time: 173ms
memory: 57552kb

Test #81:

score: 0
Accepted
time: 105ms
memory: 52144kb

Test #82:

score: 0
Accepted
time: 96ms
memory: 50172kb

Test #83:

score: 0
Accepted
time: 85ms
memory: 48100kb

Test #84:

score: 0
Accepted
time: 66ms
memory: 41960kb

Test #85:

score: 0
Accepted
time: 37ms
memory: 36904kb

Test #86:

score: 0
Accepted
time: 45ms
memory: 37140kb

Test #87:

score: 0
Accepted
time: 57ms
memory: 42452kb

Test #88:

score: 0
Accepted
time: 46ms
memory: 38264kb

Test #89:

score: 0
Accepted
time: 384ms
memory: 83528kb

Test #90:

score: 0
Accepted
time: 116ms
memory: 50220kb

Test #91:

score: 0
Accepted
time: 43ms
memory: 37904kb

Test #92:

score: 0
Accepted
time: 201ms
memory: 77024kb

Test #93:

score: 0
Accepted
time: 47ms
memory: 40488kb

Test #94:

score: 0
Accepted
time: 327ms
memory: 77892kb

Test #95:

score: 0
Accepted
time: 175ms
memory: 71924kb

Test #96:

score: 0
Accepted
time: 93ms
memory: 55488kb

Test #97:

score: 0
Accepted
time: 276ms
memory: 81980kb

Test #98:

score: 0
Accepted
time: 299ms
memory: 71752kb

Test #99:

score: 0
Accepted
time: 142ms
memory: 65452kb

Test #100:

score: 0
Accepted
time: 155ms
memory: 66924kb

Test #101:

score: 0
Accepted
time: 219ms
memory: 79656kb

Test #102:

score: 0
Accepted
time: 175ms
memory: 75112kb

Test #103:

score: 0
Accepted
time: 324ms
memory: 79120kb

Test #104:

score: 0
Accepted
time: 74ms
memory: 44740kb

Test #105:

score: 0
Accepted
time: 152ms
memory: 62784kb

Test #106:

score: 0
Accepted
time: 96ms
memory: 51500kb

Test #107:

score: 0
Accepted
time: 299ms
memory: 75916kb

Test #108:

score: 0
Accepted
time: 372ms
memory: 85628kb

Test #109:

score: 0
Accepted
time: 208ms
memory: 60348kb

Test #110:

score: 0
Accepted
time: 262ms
memory: 77304kb

Test #111:

score: 0
Accepted
time: 167ms
memory: 61004kb

Test #112:

score: 0
Accepted
time: 173ms
memory: 72884kb

Test #113:

score: 0
Accepted
time: 42ms
memory: 37088kb

Test #114:

score: 0
Accepted
time: 25ms
memory: 35408kb

Test #115:

score: 0
Accepted
time: 50ms
memory: 39192kb

Test #116:

score: 0
Accepted
time: 168ms
memory: 72252kb

Test #117:

score: 0
Accepted
time: 216ms
memory: 81408kb

Test #118:

score: 0
Accepted
time: 41ms
memory: 36160kb

Test #119:

score: 0
Accepted
time: 19ms
memory: 36020kb

Test #120:

score: 0
Accepted
time: 239ms
memory: 68040kb

Test #121:

score: 0
Accepted
time: 57ms
memory: 38956kb

Test #122:

score: 0
Accepted
time: 85ms
memory: 51744kb

Test #123:

score: 0
Accepted
time: 54ms
memory: 37624kb

Test #124:

score: 0
Accepted
time: 55ms
memory: 41648kb

Test #125:

score: 0
Accepted
time: 138ms
memory: 50920kb

Test #126:

score: 0
Accepted
time: 35ms
memory: 37036kb

Test #127:

score: 0
Accepted
time: 32ms
memory: 35040kb

Test #128:

score: 0
Accepted
time: 71ms
memory: 57980kb

Test #129:

score: 0
Accepted
time: 54ms
memory: 40240kb

Test #130:

score: 0
Accepted
time: 149ms
memory: 62252kb

Test #131:

score: 0
Accepted
time: 37ms
memory: 36792kb

Test #132:

score: 0
Accepted
time: 211ms
memory: 59904kb

Test #133:

score: 0
Accepted
time: 38ms
memory: 37052kb

Test #134:

score: 0
Accepted
time: 83ms
memory: 46308kb

Test #135:

score: 0
Accepted
time: 352ms
memory: 86572kb

Test #136:

score: 0
Accepted
time: 38ms
memory: 36120kb

Test #137:

score: 0
Accepted
time: 55ms
memory: 38376kb

Test #138:

score: 0
Accepted
time: 372ms
memory: 88420kb

Test #139:

score: 0
Accepted
time: 40ms
memory: 36352kb

Test #140:

score: 0
Accepted
time: 85ms
memory: 50596kb

Test #141:

score: 0
Accepted
time: 255ms
memory: 72180kb

Test #142:

score: 0
Accepted
time: 72ms
memory: 41212kb

Test #143:

score: 0
Accepted
time: 471ms
memory: 90620kb

Test #144:

score: 0
Accepted
time: 146ms
memory: 53596kb

Test #145:

score: 0
Accepted
time: 282ms
memory: 67640kb

Test #146:

score: 0
Accepted
time: 71ms
memory: 45372kb

Test #147:

score: 0
Accepted
time: 273ms
memory: 83676kb

Test #148:

score: 0
Accepted
time: 362ms
memory: 76800kb

Test #149:

score: 0
Accepted
time: 183ms
memory: 63216kb

Test #150:

score: 0
Accepted
time: 342ms
memory: 77800kb

Test #151:

score: 0
Accepted
time: 415ms
memory: 99308kb

Test #152:

score: 0
Accepted
time: 44ms
memory: 37540kb

Test #153:

score: 0
Accepted
time: 35ms
memory: 37808kb

Test #154:

score: 0
Accepted
time: 71ms
memory: 42532kb

Test #155:

score: 0
Accepted
time: 308ms
memory: 72336kb

Test #156:

score: 0
Accepted
time: 74ms
memory: 44744kb

Test #157:

score: 0
Accepted
time: 67ms
memory: 53036kb

Test #158:

score: 0
Accepted
time: 92ms
memory: 50852kb

Test #159:

score: 0
Accepted
time: 42ms
memory: 36076kb

Test #160:

score: 0
Accepted
time: 50ms
memory: 37280kb

Test #161:

score: 0
Accepted
time: 124ms
memory: 48320kb

Test #162:

score: 0
Accepted
time: 50ms
memory: 39248kb

Test #163:

score: 0
Accepted
time: 28ms
memory: 34516kb

Test #164:

score: 0
Accepted
time: 173ms
memory: 58212kb

Test #165:

score: 0
Accepted
time: 261ms
memory: 80432kb

Test #166:

score: 0
Accepted
time: 263ms
memory: 71924kb