oj.uz

Submission #529142

# Submission time Handle Problem Language Result Execution time Memory
529142 2022-02-22T10:14:40 Z cpp219 Zoltan (COCI16_zoltan) C++17
21 / 140
 49 ms 4520 KB 
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e5 + 9;
const ll mod = 1e9 + 7;
const ll lg = 20;

ll n,m,a[N],kq[N],tmp[N],have;

ll bpow(ll a,ll b){
    ll res = 1;
    while(b){
        if (b & 1) res = (res*a)%mod;
        a = (a * a)%mod; b >>= 1;
    }
    return res;
}

void process(){
    fill(tmp,tmp + n + 1,mod);
    for (ll i = n;i > 0;i--){
        ll pos = lower_bound(tmp,tmp + n + 1,a[i]) - tmp;
        kq[i] += pos; tmp[pos] = a[i];
    }
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n;
    for (ll i = 1;i <= n;i++) cin>>a[i];
    process();
    //for (ll i = 1;i <= n;i++) cout<<kq[i]<<" "; return 0;
    for (ll i = 1;i <= n;i++) a[i] *= -1;
    process(); ll mx = 0;
    for (ll i = 1;i <= n;i++) mx = max(mx,kq[i] + 1);
    for (ll i = 1;i <= n;i++) have += ((kq[i] + 1) == mx);
    long long res = bpow(2,n - mx);
    cout<<mx<<" "<<(res*have)%mod;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message

zoltan.cpp: In function 'int main()':
zoltan.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Incorrect 1 ms 344 KB Output isn't correct
9 Incorrect 1 ms 328 KB Output isn't correct
10 Incorrect 1 ms 332 KB Output isn't correct
11 Incorrect 28 ms 3268 KB Output isn't correct
12 Incorrect 26 ms 2888 KB Output isn't correct
13 Incorrect 24 ms 2756 KB Output isn't correct
14 Incorrect 34 ms 3304 KB Output isn't correct
15 Incorrect 37 ms 3968 KB Output isn't correct
16 Incorrect 43 ms 4520 KB Output isn't correct
17 Incorrect 38 ms 3812 KB Output isn't correct
18 Incorrect 49 ms 3832 KB Output isn't correct
19 Incorrect 40 ms 3816 KB Output isn't correct
20 Incorrect 37 ms 3784 KB Output isn't correct