QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#285248 | #7943. LIS on Grid | ucup-team266# | WA | 5ms | 3656kb | C++14 | 7.0kb | 2023-12-16 17:27:02 | 2023-12-16 17:27:02 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) int((x).size())
#ifndef local
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
using namespace std;
using ll = long long;
template<class T> inline T& cmin(T& a, const T& b) { if(b < a) a = b; return a; }
template<class T> inline T& cmax(T& a, const T& b) { if(a < b) a = b; return a; }
template<class... Args> void print(Args&&... args) {
((cout << args << ' '), ...);
}
template<class... Args> void println(Args&&... args) {
print(args...), cout << endl;
}
using u32 = uint32_t;
using u64 = uint64_t;
constexpr ll safe_mod(ll x, ll m) { return x %= m, x < 0 ? x + m : x; }
constexpr ll pow_mod_constexpr(ll x, ll n, int m) {
if(m == 1) return 0;
u32 _m = m; u64 r = 1, _x = safe_mod(x, m);
for(; n; n >>= 1, _x = _x * _x % _m) if(n & 1) r = r * _x % m;
return r;
}
constexpr bool is_prime_constexpr(int n) {
if(n <= 1) return false;
if(n == 2 || n == 7 || n == 61) return true;
if(n % 2 == 0) return false;
ll d = n - 1; while(~d & 1) d /= 2;
for(ll a : {2, 7, 61}) {
ll t = d, y = pow_mod_constexpr(a, t, n);
while(t != n - 1 && y != 1 && y != n - 1) y = y * y % n, t <<= 1;
if(y != n - 1 && t % 2 == 0) return false;
}
return true;
}
constexpr pair<ll, ll> inv_gcd(ll a, ll b) {
a = safe_mod(a, b);
if(a == 0) return {b, 0};
ll s = b, t = a, m0 = 0, m1 = 1;
while(t) {
ll u = s / t; s -= t * u, m0 -= m1 * u;
ll tmp = s; s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
}
if(m0 < 0) m0 += b / s;
return {s, m0};
}
struct barrett {
u32 m; u64 im;
barrett(u32 m) :m(m), im(~0ull / m + 1) {}
u32 mul(u32 a, u32 b) const {
u64 z = (u64)a * b, x = (__uint128_t)z * im >> 64; u32 v = z - x * m;
return m <= v ? v + m : v;
}
};
template<int m> struct static_modint {
using mint = static_modint;
public:
static mint raw(int v) { mint x; return x._v = v, x; }
static_modint() :_v(0) {}
template<class T> static_modint(T v) { ll x = v % m; _v = x < 0 ? x + m : x; }
u32 val()const { return _v; }
mint& operator++() { if(++_v == m) _v = 0; return *this; }
mint& operator--() { if(!_v--) _v = m - 1; return *this; }
mint operator++(int) { mint res = *this; ++*this; return res; }
mint operator--(int) { mint res = *this; --*this; return res; }
mint& operator+=(const mint& rhs) { _v += rhs._v; if(_v >= m) _v -= m; return *this; }
mint& operator-=(const mint& rhs) { _v -= rhs._v; if(_v >= m) _v += m; return *this; }
mint& operator*=(const mint& rhs) { u64 z = _v; z *= rhs._v, _v = z % m; return *this; }
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+()const { return *this; }
mint operator-()const { return mint() - *this; }
mint pow(ll n)const { assert(0 <= n); mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
mint inv() const{ if(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } }
friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }
friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }
friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }
friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }
friend bool operator==(const mint& lhs, const mint& rhs) { return lhs._v == rhs._v; }
friend bool operator!=(const mint& lhs, const mint& rhs) { return lhs._v != rhs._v; }
private:
u32 _v;
static constexpr bool prime = is_prime_constexpr(m);
};
template<int id> struct dynamic_modint {
using mint = dynamic_modint;
public:
static void set_mod(int m) { assert(1 <= m), bt = barrett(m); }
static mint raw(int v) { mint x; return x._v = v, x; }
dynamic_modint() :_v(0) {}
template<class T> dynamic_modint(T v) { ll x = v % (int)bt.m; _v = x < 0 ? x + bt.m : x; }
u32 val()const { return _v; }
mint& operator++() { if(++_v == bt.m) _v = 0; return *this; }
mint& operator--() { if(!_v--) _v = bt.m - 1; return *this; }
mint operator++(int) { mint res = *this; ++*this; return res; }
mint operator--(int) { mint res = *this; --*this; return res; }
mint& operator+=(const mint& rhs) { _v += rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
mint& operator-=(const mint& rhs) { _v += bt.m - rhs._v; if(_v >= bt.m) _v -= bt.m; return *this; }
mint& operator*=(const mint& rhs) { _v = bt.mul(_v, rhs._v); return *this; }
mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
mint operator+()const { return *this; }
mint operator-()const { return mint() - *this; }
mint pow(ll n)const { assert(0 <= n); mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
mint inv()const { auto eg = inv_gcd(_v, bt.m); assert(eg.first == 1); return eg.second; }
friend mint operator+(const mint& lhs, const mint& rhs) { return mint(lhs) += rhs; }
friend mint operator-(const mint& lhs, const mint& rhs) { return mint(lhs) -= rhs; }
friend mint operator*(const mint& lhs, const mint& rhs) { return mint(lhs) *= rhs; }
friend mint operator/(const mint& lhs, const mint& rhs) { return mint(lhs) /= rhs; }
friend bool operator==(const mint& lhs, const mint& rhs) { return lhs._v == rhs._v; }
friend bool operator!=(const mint& lhs, const mint& rhs) { return lhs._v != rhs._v; }
private:
u32 _v;
static barrett bt;
};
template<int id> barrett dynamic_modint<id>::bt = 998244353;
using mint = static_modint<998244353>;
ostream& operator << (ostream& os, mint a) {
return os << a.val();
}
int n, m;
void solve() {
cin >> n >> m;
int a[m];
For(i, 0, m) cin >> a[i];
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) >> 1;
ll sum = 0;
For(i, 0, m) sum += max(a[i] - mid, 0);
sum <= mid * (n - mid) ? r = mid - 1 : l = mid + 1;
}
int ans = l;
int b[m];
For(i, 0, m) b[i] = max(a[i] - ans, 0), a[i] -= b[i];
cout << ans << '\n';
char s[n][m];
mem(s, '.');
rep(k, n - ans, n - 1) {
int p = k;
For(i, 0, m) {
if (a[i]) s[p][i] = '#', a[i]--;
while (p && b[i]) s[--p][i] = '#', b[i]--;
}
}
For(i, 0, n) {
For(j, 0, m) cout << s[i][j];
cout << '\n';
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--)
solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
input:
4 2 4 1 1 1 1 3 3 3 3 3 4 4 4 3 2 1 4 5 2 3 4 3 2
output:
1 .... #### 3 ### ### ### 2 #### #... ###. ##.. 2 ..### .#### ####. ###..
result:
ok Correct (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 5ms
memory: 3656kb
input:
5699 5 5 4 5 1 3 5 4 4 3 1 2 4 5 5 2 2 3 3 4 3 4 1 3 2 2 5 5 2 5 3 4 4 4 5 4 1 1 4 1 5 5 3 3 2 5 5 5 5 3 1 3 1 1 5 5 2 4 4 3 2 4 5 2 2 2 2 2 5 5 4 5 3 4 1 5 4 5 4 1 4 5 4 1 1 1 3 4 2 2 4 5 5 2 5 5 2 5 5 5 5 1 2 1 3 5 5 4 4 2 2 3 5 2 5 2 3 5 2 3 3 1 3 5 5 4 2 5 1 1 5 5 4 5 4 1 5 5 4 3 2 5 3 5 5 5 4 1...
output:
3 .#### ##..# ##.## ##... ##.## 2 ...# #### #..# #.## 2 ....# ...## ..##. ###.# ##### 2 .### ##.. .### 3 .#### .#..# ##.## ####. .#### 2 ##### #..#. #..#. #..#. 3 ...## ...## ##### ##### ##.## 1 ..### ..#.. ###.. #.... #.... 2 ..### .##.. .#.## ####. ###.. 2 ..... ..... ##### ##### 3 .#### ##.#. ###...
result:
wrong answer Wrong number of colored cells (test case 1)