Submission #577174

#	Time	Username	Problem	Language	Result	Execution time	Memory
577174		Ronin13	Zoltan (COCI16_zoltan)	C++14	21 / 140	1084 ms	4532 KiB

zoltan

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;

const ll mod = 1e9 + 7;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int a[n + 1];
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    deque <int> q;
    q.push_front(a[1]);
    for(int i = 2; i <= n; i++){
        if(a[i] > q.front()) q.push_back(a[i]);
        else q.push_front(a[i]);
    }
    int b[n + 1];
    int ind = 0;
    while(!q.empty()){
        int v = q.front();
        q.pop_front();
        b[ind++] = v;
    }
    ll cnt = 0;
    int mx = 0;
    for(int i = 0; i < (1 << n); i++){
        vector <int> vec;
        for(int j = 0; j < n; j++) if((1 << j) & i) vec.pb(b[j]);
        int ind = false;
        for(int j = 1; j < vec.size(); j++){
            if(vec[j] <= vec[j - 1]){
                ind = true;
                break;
            }
        }
        if(!ind){
            mx = max(mx, (int)vec.size());
        }
    }
    for(int i = 0; i < (1 << n); i++){
        if(__builtin_popcount(i) != mx) continue;
        vector <int> vec;
        for(int j = 0; j < n; j++) if((1 << j) & i) vec.pb(b[j]);
        int ind = false;
        for(int j = 1; j < vec.size(); j++){
            if(vec[j] <= vec[j - 1]){
                ind = true;
                break;
            }
        }
        if(!ind){
            cnt++;
        }
    }
    for(int i = 1; i <= n - mx; i++) cnt *= 2, cnt %= mod;
    cout << mx << ' ' << cnt << "\n";
    return 0;
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = 1; j < vec.size(); j++){
      |                        ~~^~~~~~~~~~~~
zoltan.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j = 1; j < vec.size(); j++){
      |                        ~~^~~~~~~~~~~~

• Subtask 1: 21 / 140