QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#286233 | #7943. LIS on Grid | ucup-team2894# | WA | 6ms | 3564kb | C++20 | 5.8kb | 2023-12-17 06:53:54 | 2023-12-17 06:53:55 |
Judging History
answer
// UW BLACK
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)((x).size()))
#define rep(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int,int>;
mt19937 rnd(223);
clock_t TIME0;
#define TIME ((clock() - TIME0) * 1.0 / CLOCKS_PER_SEC)
constexpr int maxn = 1e6 + 100, inf = 1e9 + 100;
const ll mod = 1e9+7;
using T = long double;
constexpr const T EPS = 1e-9;
bool lt(T a, T b) { return a + EPS < b; }
bool le(T a, T b) { return !lt(b, a); }
bool gt(T a, T b) { return lt(b, a); }
bool ge(T a, T b) { return !lt(a, b); }
bool eq(T a, T b) { return !lt(a, b) && !lt(b, a); }
bool ne(T a, T b) { return lt(a, b) || lt(b, a); }
int sgn(T a) { return lt(a, 0) ? -1 : lt(0, a) ? 1 : 0; }
#define OP(op, U, a, x, y) \
pt operator op (U a) const { return pt(x, y); } \
pt &operator op##= (U a) { return *this = *this op a; }
#define CMP(op, body) \
bool operator op (pt p) const { return body; }
struct pt {
T x, y; constexpr pt(T x = 0, T y = 0) : x(x), y(y) {}
pt operator + () const { return *this; }
pt operator - () const { return pt(-x, -y); }
OP(+, pt, p, x + p.x, y + p.y) OP(-, pt, p, x - p.x, y - p.y)
OP(*, T, a, x * a, y * a) OP(/, T, a, x / a, y / a)
friend pt operator * (T a, pt p) {
return pt(a * p.x, a * p.y);
}
bool operator < (pt p) const {
return eq(x, p.x) ? lt(y, p.y) : lt(x, p.x);
}
CMP(<=, !(p < *this)) CMP(>, p < *this) CMP(>=, !(*this < p))
CMP(==, !(*this < p) && !(p < *this))
CMP(!=, *this < p || p < *this)
OP(*, pt, p, x * p.x - y * p.y, y * p.x + x * p.y)
OP(/, pt, p, (x * p.x + y * p.y) / (p.x * p.x + p.y * p.y),
(y * p.x - x * p.y) / (p.x * p.x + p.y * p.y))
};
#undef OP
#undef CMP
istream &operator >> (istream &stream, pt &p) {
return stream >> p.x >> p.y;
}
ostream &operator << (ostream &stream, pt p) {
return stream << p.x << ' ' << p.y;
}
pt conj(pt a) { return pt(a.x, -a.y); }
T dot(pt a, pt b) { return a.x * b.x + a.y * b.y; }
T cross(pt a, pt b) { return a.x * b.y - a.y * b.x; }
T norm(pt a) { return dot(a, a); }
T abs(pt a) { return sqrt(norm(a)); }
T arg(pt a) { return atan2(a.y, a.x); }
pt polar(T r, T theta) {
return r * pt(cos(theta), sin(theta));
}
T distSq(pt a, pt b) { return norm(b - a); }
T dist(pt a, pt b) { return abs(b - a); }
T ang(pt a, pt b) { return arg(b - a); }
T ang(pt a, pt b, pt c) {
a -= b; c -= b; return arg(pt(dot(c, a), cross(c, a)));
}
T area2(pt a, pt b, pt c) { return cross(b - a, c - a); }
int ccw(pt a, pt b, pt c) { return sgn(area2(a, b, c)); }
pt rot(pt a, pt p, T theta) {
return (a - p) * pt(polar(T(1), theta)) + p;
}
pt perp(pt a) { return pt(-a.y, a.x); }
struct Circle {
pt o; T r; Circle(T r = 0) : o(0, 0), r(r) {}
Circle(pt o, T r) : o(o), r(r) {}
int contains(pt p) const {return sgn(r * r - distSq(o, p));}
int contains(Circle c) const {
T dr = r - c.r;
return lt(dr, 0) ? -1 : sgn(dr * dr - distSq(o, c.o));
}
int disjoint(Circle c) const {
T sr = r + c.r; return sgn(distSq(o, c.o) - sr * sr);
}
pt proj(pt p) const { return o + (p - o) * r / dist(o, p); }
pt inv(pt p) const { return o + (p - o)*r*r / distSq(o, p); }
};
Circle circumcircle(pt a, pt b, pt c) {
b -= a; c -= a;
pt ret = b*c*(conj(c) - conj(b)) / (b*conj(c) - conj(b)*c);
return Circle(a + ret, abs(ret));
}
Circle minEnclosingCircle(vector<pt> P) {
mt19937_64 rng(0); shuffle(P.begin(), P.end(), rng);
Circle c(P[0], 0);
rep(i, 0, P.size()) if (lt(c.r, dist(P[i], c.o))) {
c = Circle(P[i], 0);
rep(j, 0, i) if (lt(c.r, dist(P[j], c.o))) {
pt p = (P[i] + P[j])/T(2); c = Circle(p, dist(P[i], p));
rep(k, 0, j) if (lt(c.r, dist(P[k], c.o)))
c = circumcircle(P[i], P[j], P[k]);
}
}
return c;
}
vector<pt> convexHull(vector<pt> P) {
vector<pt> hull; sort(P.begin(), P.end()); rep(h, 0, 2) {
int st = hull.size(); for (auto &&p : P) {
while (int(hull.size()) >= st + 2
&& ccw(hull[hull.size() - 2], hull.back(), p) <= 0)
hull.pop_back();
hull.push_back(p);
}
hull.pop_back(); reverse(P.begin(), P.end());
}
if (int(hull.size()) == 2 && hull[0] == hull[1])
hull.pop_back();
if (hull.empty() && !P.empty()) hull.push_back(P[0]);
return hull;
}
void solve() {
int n,m;
cin >> n >> m;
vi a(m);
for(int i=0;i<m;i++)cin >> a[i];
vi pans;
auto test = [&](int k){
// cerr <<"k " << k << endl;
vi mo(n);
vi ans(m);
int base=n-1;
for(int i=0;i<m;i++){
while(base>0&&mo[base-1]+1>k)base--;
// cerr << i << " " << base << endl;
if(base-a[i]+1<0)return false;
ans[i]=base;
// cerr << i << endl;
for(int j=0;j<a[i];j++)mo[base-j]=max(mo[base-j],(base-j-1<0)?1:(mo[base-j-1]+1));
// cerr << i << endl;
}
pans=ans;
return true;
};
bool res = test(2);
// cerr << "Res " << res << endl;
int l=1,r=min(n,m);
while(l<r){
// cerr << "l r " << l << " " <<r << endl;
int mid=(l+r)/2;
if(test(mid))r=mid;
else l=mid+1;
}
test(l);
cout << l << "\n";
vector<string> o(n, string(m, '.'));
for(int i=0;i<m;i++){
for(int j=0;j<a[i];j++)o[pans[i]-j][i]='#';
}
for(int i=0;i<n;i++) cout << o[i] << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed;
cout.precision(20);
TIME0 = clock();
int k=1;
cin >> k;
while(k--)
solve();
// cerr << "\n\nConsumed " << TIME << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
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: 6ms
memory: 3520kb
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:
4 .#..# ##..# ##.## ##.## ##### 3 ...# #..# #.## #### 2 ....# ....# ..### ##### ####. 2 .#.# .### ###. 3 .#..# .#.## .#### ##### ####. 2 #..#. #..## #..#. ####. 3 ...## ...## ##.## ##### ##### 1 ..### ..#.. ###.. #.... #.... 2 ...#. .#### .#### ###.. ###.. 2 ..... ..... ##### ##### 3 .#.#. ##.#. ###...
result:
wrong answer Jury found better answer than participant (test case 1)