3818 2023. 03. 03 09:48:26 hackemon Síkság (55) cpp17 Hibás válasz 38/55 266ms 5944 KiB
#include <bits/stdc++.h>
using namespace std;
//using namespace std::chrono;

#define pii pair<int,int>
#define pb push_back
#define vi vector<int>
#define vb vector<bool>
#define vl vector<ll>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvl vector<vl>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fScan {ios_base::sync_with_stdio(false); cin.tie(NULL);}
#define rep(i, a, b) for(int i = a; i < (b); i++)
#define REP(i, n) for(int i = 0;i <(n); i++)
using ll = long long;
using ld = long double;
ll mod = 1000000007;

const char ny =  '\n';

bool prime(ll a) {
    if (a==1) return 0;
    for (int i=2;i*i<=a;++i)
    {
        if (a%i==0) return 0;
    }
    return 1;
}

ll gcd(ll a,ll b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
    return a/gcd(a,b)*b;
}

ll min(int a, ll b) {
    if(a< b) return a;
    else return b;
}


void solve() { 
    int n;
    cin >> n;
    vector<int> k(n);
    vector<int> halmazok, prefi;
    for(int i = 0;i < n;i++ ) cin >> k[i];
    
    halmazok.push_back(1);
    for(int i = 1;i< n;i++ ) {
        if(k[i] == k[i-1]) {
            halmazok[halmazok.size()-1]++;
        } else {
            halmazok.push_back(1);
        }
    }
    prefi.push_back(halmazok[0]-1);
    for(int i = 1;i< halmazok.size();i++ ) {
        prefi.push_back(prefi[prefi.size()-1] + halmazok[i]);
    }

    /*
    for(int i = 0;i< halmazok.size();i++ ) {
    cout << halmazok[i] << ' ';
    }
    cout << endl;
    for(int i = 0;i< prefi.size();i++ ) {
        cout << prefi[i] << ' ';
    }
    */

    vector<pair<int, int>> ansok;
    int index1 = 0, index2 = prefi[0];
    ansok.push_back({1 , prefi[0]+1});
    //cout << ansok[0].first << ansok[0].second << endl;
    for(int i = 1;i< halmazok.size();i++ ) {
        
        bool v = false;
        for(int j = index1;j<= index2;j++ ) {
            if(abs(k[j] - k[prefi[i]]) > 1) {
                v = true;
            }
        }
        
        if(!v) {
            index2 = prefi[i];
        } else {
            ansok.push_back({index1+1, index2+1});
            //cout << index1 << ' ' << index2 << endl;
            if(abs(k[prefi[i]] - k[prefi[i-1]] < 2) && i > 1) {
                index1 = prefi[i-2]+1;
                index2 = prefi[i];
            } else {
                index1 = prefi[i-1]+1;
                index2 = prefi[i-1] + halmazok[i];
                //cout << index2 << endl;
            }
        }
    }
    ansok.push_back({index1+1, index2+1});
    int ma = -1;
    int pos = 0;
    for(int i = 0;i< ansok.size();i++ ) {
        if(ansok[i].second - ansok[i].first > ma) {
            ma = ansok[i].second - ansok[i].first;
            //cout << ma << endl;
            pos = i;
        }
    }
    cout << ansok[pos].second - ansok[pos].first + 1<< ' ' << ansok[pos].first << endl;
    
    }


int main()
{
    fScan

    int t = 1;
    //comment out if necessary
    //cin>> t;


    //auto start = high_resolution_clock::now();
    while(t-- ) {
        solve();
    }
    //auto end = high_resolution_clock::now();
    //auto dur = duration_cast<milliseconds>(end-start);
    //cout<< "runtime: " << dur.count() << " milliseconds" << '\n';
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 38/55
1 Elfogadva 0/0 3ms 1832 KiB
2 Elfogadva 0/0 4ms 2248 KiB
3 Elfogadva 2/2 2ms 2104 KiB
4 Elfogadva 2/2 3ms 2232 KiB
5 Hibás válasz 0/2 3ms 2448 KiB
6 Elfogadva 2/2 3ms 2660 KiB
7 Elfogadva 3/3 3ms 2872 KiB
8 Elfogadva 2/2 3ms 3124 KiB
9 Elfogadva 3/3 3ms 3064 KiB
10 Elfogadva 3/3 4ms 3492 KiB
11 Elfogadva 3/3 3ms 3548 KiB
12 Elfogadva 3/3 39ms 3764 KiB
13 Hibás válasz 0/3 14ms 5096 KiB
14 Elfogadva 3/3 9ms 3984 KiB
15 Időlimit túllépés 0/3 216ms 4772 KiB
16 Elfogadva 3/3 21ms 4544 KiB
17 Elfogadva 3/3 56ms 5096 KiB
18 Hibás válasz 0/3 14ms 5868 KiB
19 Időlimit túllépés 0/3 266ms 5640 KiB
20 Elfogadva 3/3 179ms 5944 KiB
21 Elfogadva 3/3 45ms 5280 KiB
22 Hibás válasz 0/3 74ms 4808 KiB