QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#321176 | #8217. King's Dinner | ucup-team992# | WA | 0ms | 3836kb | C++20 | 5.9kb | 2024-02-04 06:23:04 | 2024-02-04 06:23:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
typedef int uci;
#define int long long
#define F first
#define S second
typedef complex<double> cd;
seed_seq seq{
(uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
(uint64_t) __builtin_ia32_rdtsc(),
(uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
// mt19937_64 lrng(seq);
struct debugger{
template <typename T>
debugger& operator<<(T &a){
#ifdef DEBUG
cerr << a;
#endif
return *this;
}
template <typename T>
debugger& operator<<(T &&a){
#ifdef DEBUG
cerr << a;
#endif
return *this;
}
} deb;
const double PI = acos(-1.0);
const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;
//! function insert
//THINK FIRST, CODE SECOND
//DON'T GET STUCK ON ONE STRATEGY
//CALM DOWNNN FOR ONCE IN YOUR LIFE
//REDUCE
//COUGH E??!?!?!! O.O
//uwu i see you ryan
int n;
bool cando(int i, int j){
return i >= 0 && i < n && j >= 0 && j < n;
}
void markbad(int i, int j, vector<vector<bool>> &good){
for(int o = -1; o <= 1; ++o){
for(int k = -1; k <= 1; ++k){
if(cando(i+o, j+k))
good[i+o][j+k] = false;
}
}
}
int wayone(vector<string> &a){
int added{};
for(int i{}; i < n; i += 3){
if(i+1 >= n){
for(int j{}; j < n; j += 3){
if(j+1 >= n)
break;
a[i][j] = a[i][j+1] = '#';
added++;
}
break;
}
for(int j{}; j < n; j += 2){
a[i][j] = a[i+1][j] = '#';
added++;
}
}
return added;
}
int waytwo(vector<string> &a){
int added{};
int x = 0, y = 0;
vector<ar<int, 2>> ds{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<vector<bool>> good(n, vector<bool>(n, true));
int dind{};
int upb = 0, lowb = n-1, leftb = 1, rightb = n-1;
for(int i{}; i < n*n; ++i){
if(dind == 0 && x == lowb){
dind++;
lowb--;
}
if(dind == 1 && y == rightb){
dind++;
rightb--;
}
if(dind == 2 && x == upb){
dind++;
upb++;
}
if(dind == 3 && y == leftb){
dind = 0;
leftb++;
}
int nex, ney;
nex = x+ds[dind][0];
ney = y+ds[dind][1];
if(good[x][y] && good[nex][ney]){
a[x][y] = '#';
a[nex][ney] = '#';
added++;
markbad(x, y, good);
markbad(nex, ney, good);
}
x = nex, y = ney;
}
return added;
}
int waythree(vector<string> &a, int l, int r, int u, int d){
int si = r-l+1;
if(si <= 1)
return 0;
if(si == 2){
a[l][l] = a[l+1][l] = '#';
return 1;
}
if(si == 3){
a[l][l] = a[l+1][l] = '#';
a[l][l+2] = a[l+1][l+2] = '#';
return 2;
}
int added{};
for(int i = l; i < r-2; i += 2){
a[u][i] = a[u+1][i] = '#';
added++;
}
for(int i = u; i < d-2; i += 2){
a[i][r] = a[i][r-1] = '#';
added++;
}
for(int i = r; i > l+2; i -= 2){
a[d][i] = a[d-1][i] = '#';
added++;
}
for(int i = d; i > u+2; i -= 2){
a[i][l] = a[i][l+1] = '#';
added++;
}
added += waythree(a, l+3, r-3, u+3, d-3);
return added;
}
int wayfour(vector<string> &a, int l, int r, int u, int d){
int added{};
for(int i = u; i <= d; i += 2){
a[i][l] = a[i][l+1] = '#';
added++;
}
for(int i = l+3; i <= r; i += 2){
a[u][i] = a[u+1][i] = '#';
added++;
}
added += waythree(a, l+3, r, u+3, d);
return added;
}
void solve() {
cin >> n;
vector<string> a(n, string(n, '.'));
vector<string> b(n, string(n, '.'));
vector<string> c(n, string(n, '.'));
vector<string> d(n, string(n, '.'));
int one = wayone(a);
int two = waytwo(b);
int three = waythree(c, 0, n-1, 0, n-1);
int four = 0;
if(n%2){
four = wayfour(d, 0,n-1, 0, n-1);
}
if(one >= two && one >= three && one >= four)
for(auto &t : a)
cout << t << '\n';
else if(two >= one && two >= three && two >= four)
for(auto &t : b)
cout << t << '\n';
else if(three >= one && three >= two && three >= four)
for(auto &t : c)
cout << t << '\n';
else
for(auto &t : d)
cout << t << '\n';
}
uci main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc; cin >> tc;
for (int t = 1; t <= tc; t++) {
// cout << "Case #" << t << ": ";
solve();
}
}
/*
random number generator stuff
num = rng(); gives integer number
num = uniform_int_distribution<int>(a, b)(rng); -> bounds [a, b]
num = uniform_real_distribution<double>(a, b)(rng); -> bounds [a, b)
can also instantiate distributions and call on generator:
uniform_int_distribution<int> thing(a, b);
num = thing(rng);
*/
// struct custom_hash {
// static uint64_t splitmix64(uint64_t x) {
// // http://xorshift.di.unimi.it/splitmix64.c
// x += 0x9e3779b97f4a7c15;
// x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
// x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
// return x ^ (x >> 31);
// }
// size_t operator()(uint64_t x) const {
// static const uint64_t FIXED_RANDOM = lrng();
// return splitmix64(x + FIXED_RANDOM);
// }
// };
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3836kb
input:
3 1 2 3
output:
# #. #. #.# #.# ...
result:
wrong answer grid has a singular #, not a domino, in it (test case 1)