QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#286233#7943. LIS on Griducup-team2894#WA 6ms3564kbC++205.8kb2023-12-17 06:53:542023-12-17 06:53:55

Judging History

你现在查看的是最新测评结果

  • [2023-12-17 06:53:55]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3564kb
  • [2023-12-17 06:53:54]
  • 提交

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;
}

详细

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)