QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#284599 | #7943. LIS on Grid | ucup-team2230# | WA | 15ms | 3496kb | C++17 | 3.2kb | 2023-12-16 14:01:12 | 2023-12-16 14:01:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mp make_pair
#define fr first
#define sc second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define rep_(_1,_2,_3,NAME,...) NAME
#define rep(...) rep_(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define rep1(i,j) for(int i=0;i<(j);i++)
#define rep2(i,j,k) for(int i=(j);i<(k);i++)
template<class T> T T_INF(){ return 1000000000000000000; }
template<> int T_INF<int>(){ return 1000000000; }
ll n,m;
ll a[200010];
bool f(int X){
vector<int> b(n);
for(int i=0;i<m;i++){
int z=a[i];
if(z>0){
for(int j=0;j<n;j++){
if((j==0&&b[j]>0)||(j!=0&&b[j-1]<b[j])){
z--;
if(z==0)break;
}
}
}
if(z>0){
for(int j=n-1;j>=0;j--){
if(((j!=0&&b[j]==b[j-1])||(j==0&&b[j]==0))&&b[j]<X){
z--;
b[j]++;
if(z==0)break;
}
}
}
if(z>0)return false;
}
return true;
}
void g(int X){
vector<int> b(n);
vector<string> S(n,string(m,'.'));
for(int i=0;i<m;i++){
int z=a[i];
if(z>0){
for(int j=0;j<n;j++){
if((j==0&&b[j]>0)||(j!=0&&b[j-1]<b[j])){
z--;
S[j][i]='#';
if(z==0)break;
}
}
}
if(z>0){
for(int j=n-1;j>=0;j--){
if(((j!=0&&b[j]==b[j-1])||(j==0&&b[j]==0))&&b[j]<X){
z--;
S[j][i]='#';
b[j]++;
if(z==0)break;
}
}
}
}
rep(i,n)cout<<S[i]<<endl;
}
void solve(){
int l=0,r=n;
while(l<r){
int mid=(l+r)/2;
if(f(mid))r=mid;
else l=mid+1;
}
cout<<l<<endl;
g(l);
}
/*void solve(){
const int inf = 1000000000;
vector dp(m+1,vector(n+1,inf));
vector pre(m+1,vector(n+1,-1));
dp[0][0]=0;
rep(i,m){
rep(j,n+1){
if(dp[i][j] == inf)continue;
if(dp[i][j] > j*n-j*(j-1)/2)continue;
if(dp[i+1][j] > dp[i][j]+max(a[i]-j,0LL)){
dp[i+1][j] = dp[i][j]+max(a[i]-j,0LL);
pre[i+1][j] = j;
}
if(dp[i+1][j+1] > dp[i][j]+max(a[i]-j,0LL)){
dp[i+1][j+1] = dp[i][j]+max(a[i]-j,0LL);
pre[i+1][j+1] = j;
}
}
}
int ret=inf;
int j_=-1;
for(int j=n;j>=0;j--){
if(dp[m][j] <= j*n-j*(j-1)/2){
ret=j_=j;
}
}
vector<int> js(m);
for(int i=m;i>0;i--){
js[i-1]=j_;
j_=pre[i][j_];
}
vector<string> S(n,string(m,'.'));
vector<int> b(n);
rep(i,m){
vector<int> temp;
if(js[i]>b[n-1]){
temp.push_back(n-1);
}
if(b[0]>0)temp.push_back(0);
for(int i=1;i<n-1;i++){
}
}
cout<<ret<<endl;
}*/
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.precision(20);
int T;
cin>>T;
rep(t,T){
cin>>n>>m;
rep(i,m)cin>>a[i];
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
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: 15ms
memory: 3488kb
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 Jury found better answer than participant (test case 21)