38172023-03-03 09:46:21hackemonSíkság (55)cpp17Hibás válasz 36/55266ms6164 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] - 1;
                //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ÖsszpontTesztVerdiktIdőMemória
base36/55
1Elfogadva0/03ms1828 KiB
2Elfogadva0/04ms2252 KiB
3Hibás válasz0/23ms2240 KiB
4Elfogadva2/23ms2604 KiB
5Hibás válasz0/23ms2684 KiB
6Elfogadva2/23ms2924 KiB
7Elfogadva3/33ms3160 KiB
8Elfogadva2/23ms3400 KiB
9Elfogadva3/33ms3460 KiB
10Elfogadva3/34ms4012 KiB
11Elfogadva3/33ms3988 KiB
12Elfogadva3/339ms4164 KiB
13Hibás válasz0/314ms5480 KiB
14Elfogadva3/39ms4440 KiB
15Időlimit túllépés0/3216ms5320 KiB
16Elfogadva3/321ms4788 KiB
17Elfogadva3/356ms5180 KiB
18Hibás válasz0/314ms6012 KiB
19Időlimit túllépés0/3266ms6108 KiB
20Elfogadva3/3179ms6164 KiB
21Elfogadva3/345ms5820 KiB
22Hibás válasz0/374ms5252 KiB