Submission #1013770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013770		ReLice	Building 4 (JOI20_building4)	C++17	0 / 100	2093 ms	141980 KiB

building4

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
//#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;

template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
const ll inf=1e18+7;
const ll mod=1e9+7;
const ll N=3e3+7;
const ld eps=1e-9;
ll dp[N][N][2];
str s1(ll n,vll a,vll b){
    ll i,j;
    memset(dp,0ll,sizeof(dp));
    dp[1][0][0]=1;
    dp[0][1][1]=1;
    for(ll len=1;len<2*n;len++){
        for(i=0;i<=len;i++){
            j=len-i;
            ll x=i+j-1;
            if(i>n || j>n)continue;
            if(i<n && a[x]<=a[x+1])dp[i+1][j][0]+=dp[i][j][0];
            if(j<n && a[x]<=b[x+1])dp[i][j+1][1]+=dp[i][j][0];
            if(i<n && b[x]<=a[x+1])dp[i+1][j][0]+=dp[i][j][1];
            if(j<n && b[x]<=b[x+1])dp[i][j+1][1]+=dp[i][j][1];
        }
    }
    if(!dp[n][n][0] && !dp[n][n][1]) { return "";}
    ll A=n,B=n,c,x=n*2-1;
    if(dp[n][n][0])c=0;
    else c=1;
    str ans;
    while(x){
        if(c==0){
            ans+='A';
            A--;
            if(!A || a[x]<a[x-1] || !dp[A][B][0]) c=1;
            x--;
        }else{
            ans+='B';
            B--;
            if(!B || b[x]<b[x-1] || !dp[A][B][1]) c=0;
            x--;
        }
    }
    if(A) ans+='A';
    else ans+='B';
    reverse(all(ans));
    return ans;
}
bool s2(str ans,vll a,vll b){
    ll i;
    vll v,v2;
    for(i=0;i<ans.sz;i++){
        if(ans[i]=='A')v.pb(a[i]);
        else v.pb(b[i]);
    }
    v2=v;
    sort(all(v2));
    if(v!=v2)return false;
    return true;
}

signed main(){
    ll i;
    while(true){
        ll n=rnd(1,5);
        vll a(n*2),b(n*2);
        for(auto &i : a) i=rnd(1,10);
        for(auto &i : b) i=rnd(1,10);

        if(!s2(s1(n,a,b),a,b)){
            cout<<"Bad"<<endl;
            cout<<n<<endl;
            for(auto i : a) cout<<i<<' ';cout<<endl;
            for(auto i : b) cout<<i<<' ';cout<<endl;
            cout<<s1(n,a,b)<<endl;
            return 0;
        }
        cout<<"Passed"<<endl;
    }
	return 0;
}
/*

*/

Compilation message (stderr)

building4.cpp: In function 'bool s2(std::string, std::vector<long long int>, std::vector<long long int>)':
building4.cpp:81:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(i=0;i<ans.sz;i++){
      |              ^
building4.cpp: In function 'int main()':
building4.cpp:102:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  102 |             for(auto i : a) cout<<i<<' ';cout<<endl;
      |             ^~~
building4.cpp:102:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  102 |             for(auto i : a) cout<<i<<' ';cout<<endl;
      |                                          ^~~~
building4.cpp:103:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  103 |             for(auto i : b) cout<<i<<' ';cout<<endl;
      |             ^~~
building4.cpp:103:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  103 |             for(auto i : b) cout<<i<<' ';cout<<endl;
      |                                          ^~~~
building4.cpp:92:8: warning: unused variable 'i' [-Wunused-variable]
   92 |     ll i;
      |        ^

• Subtask 1: 0 / 11
• Subtask 2: 0 / 89