QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#321076 | #8217. King's Dinner | ucup-team992# | WA | 1ms | 3724kb | C++20 | 4.3kb | 2024-02-04 03:11:08 | 2024-02-04 03:11:09 |
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;
}
void solve() {
cin >> n;
vector<string> a(n, string(n, '.'));
vector<string> b(n, string(n, '.'));
int one = wayone(a);
int two = waytwo(b);
if(one >= two)
for(auto &t : a)
cout << t << '\n';
else
for(auto &t : b)
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);
// }
// };
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3660kb
input:
3 1 2 3
output:
. #. #. #.# #.# ...
result:
ok all tests correct (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3724kb
input:
50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
output:
. #. #. #.# #.# ... #.## #... ...# ##.# #.#.# #.#.# ..... #.#.# #.#.# #.##.. #....# ..#..# #.#... #....# ..##.# #.#.#.# #.#.#.# ....... #.#.#.# #.#.#.# ....... ##.##.. #.#.#.#. #.#.#.#. ........ #.#.#.#. #.#.#.#. ........ #.#.#.#. #.#.#.#. #.#.#.#.# #.#.#.#.# ......... #.#.#.#.# #.#.#.#.# ......... ...
result:
wrong answer jury has the better answer: jans = 8, pans = 7 (test case 6)