AtCoder Regular Contest 001

Submission #6872659

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }
template<class Type>struct is_vector : std::false_type {};
template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
template <typename T> inline ostream& operator << (ostream& out, const vector<T>& v) {
	if (v.empty())return out;
	constexpr bool is_vector_v = is_vector<T>::value;
	if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
	else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
	return out;
}
inline void put() {}
template<class T> inline void put(const T& first) { std::cout << first; printf("\n"); }
template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first; printf(" "); put(rest...); }
inline void putn() {}
template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first; printf("\n"); putn(rest...); }

vector<string> res;

void dfs(vector<string> s,vector<int> c) {
	bool cflag = true;
	REP(i, 8) {
		cflag &= c[i];
	}
	if (cflag) {
		int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
		int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
		vector<vector<int>> a(8, vector<int>(8, 0));
		REP(i, 8) {
			REP(j, 8) {
				if (s[i][j] == 'Q') {
					REP(k, 8) {
						REP(l, 8) {
							int ny = i + dy[l] * k;
							int nx = j + dx[l] * k;
							if (0 <= ny && ny < 8 && 0 <= nx && nx < 8) {
								a[ny][nx] = 1;
								if (k != 0 && s[ny][nx] == 'Q') {
									return;
								}
							}
						}
					}
				}
			}
		}
		res = s;
	}
	REP(i, 8) {
		if (c[i]==0) {
			c[i] = 1;
			REP(j, 8) {
				vector<string> s1 = s;
				s1[i][j] = 'Q';
				dfs(s1, c);
			}
			break;
		}
	}
}

int main() {
	vector<string> s(8);
	REP(i, 8) {
		cin >> s[i];
	}
	vector<int> c(8, 0);
	REP(i, 8) {
		REP(j, 8) {
			if (s[i][j] == 'Q') {
				c[i] = 1;
			}
		}
	}
	dfs(s, c);
	if (res.size()) {
		REP(i, 8) {
			put(res[i]);
		}
	} else {
		put("No Answer");
	}
	
	return 0;
}

Submission

Task問題 C - パズルのお手伝い
User nameユーザ名 idaten
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2937 Byte
File nameファイル名
Exec time実行時間 274 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 00_sample1.txt,00_sample2.txt,01_rnd_00.txt,01_rnd_01.txt,01_rnd_02.txt,01_rnd_03.txt,01_rnd_04.txt,01_rnd_05.txt,01_rnd_06.txt,01_rnd_07.txt,01_rnd_08.txt,01_rnd_09.txt,01_rnd_10.txt,01_rnd_11.txt,01_rnd_12.txt,01_rnd_13.txt,01_rnd_14.txt,01_rnd_15.txt,01_rnd_16.txt,01_rnd_17.txt,01_rnd_18.txt,01_rnd_19.txt,01_rnd_20.txt,01_rnd_21.txt,01_rnd_22.txt,01_rnd_23.txt,01_rnd_24.txt,01_rnd_25.txt,01_rnd_26.txt,01_rnd_27.txt,01_rnd_28.txt,01_rnd_29.txt,01_rnd_30.txt,01_rnd_31.txt,01_rnd_32.txt,01_rnd_33.txt,01_rnd_34.txt,01_rnd_35.txt,01_rnd_36.txt,01_rnd_37.txt,01_rnd_38.txt,01_rnd_39.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample1.txt AC 44 ms 256 KB
00_sample2.txt AC 37 ms 256 KB
01_rnd_00.txt AC 38 ms 256 KB
01_rnd_01.txt AC 35 ms 256 KB
01_rnd_02.txt AC 267 ms 256 KB
01_rnd_03.txt AC 37 ms 256 KB
01_rnd_04.txt AC 264 ms 256 KB
01_rnd_05.txt AC 34 ms 256 KB
01_rnd_06.txt AC 270 ms 256 KB
01_rnd_07.txt AC 231 ms 256 KB
01_rnd_08.txt AC 33 ms 256 KB
01_rnd_09.txt AC 274 ms 256 KB
01_rnd_10.txt AC 35 ms 256 KB
01_rnd_11.txt AC 274 ms 256 KB
01_rnd_12.txt AC 35 ms 256 KB
01_rnd_13.txt AC 35 ms 256 KB
01_rnd_14.txt AC 35 ms 256 KB
01_rnd_15.txt AC 34 ms 256 KB
01_rnd_16.txt AC 248 ms 256 KB
01_rnd_17.txt AC 30 ms 256 KB
01_rnd_18.txt AC 36 ms 256 KB
01_rnd_19.txt AC 35 ms 256 KB
01_rnd_20.txt AC 271 ms 256 KB
01_rnd_21.txt AC 262 ms 256 KB
01_rnd_22.txt AC 36 ms 256 KB
01_rnd_23.txt AC 37 ms 256 KB
01_rnd_24.txt AC 268 ms 256 KB
01_rnd_25.txt AC 35 ms 256 KB
01_rnd_26.txt AC 34 ms 256 KB
01_rnd_27.txt AC 36 ms 256 KB
01_rnd_28.txt AC 35 ms 256 KB
01_rnd_29.txt AC 35 ms 256 KB
01_rnd_30.txt AC 36 ms 256 KB
01_rnd_31.txt AC 267 ms 256 KB
01_rnd_32.txt AC 35 ms 256 KB
01_rnd_33.txt AC 267 ms 256 KB
01_rnd_34.txt AC 35 ms 256 KB
01_rnd_35.txt AC 235 ms 256 KB
01_rnd_36.txt AC 36 ms 256 KB
01_rnd_37.txt AC 36 ms 256 KB
01_rnd_38.txt AC 35 ms 256 KB
01_rnd_39.txt AC 35 ms 256 KB