QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72129#4803. Candiesricky0129TL 2ms3664kbC++142.0kb2023-01-14 12:41:022023-01-14 12:41:04

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-14 12:41:04]
  • Judged
  • Verdict: TL
  • Time: 2ms
  • Memory: 3664kb
  • [2023-01-14 12:41:02]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define FOR(i,n) for(int i=0;i<n;i++)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second

const int MOD = (int)1e9+7;

int main()
{
    ll n,x;
    scanf("%lld%lld",&n,&x);
    ll A[n];
    FOR(i,n) scanf("%lld",&A[i]);
    set<int> pos;
    priority_queue<pair<int,pii> > pq;
    FOR(i,n){
        pos.insert(i);
        if(A[i]==A[(i+1)%n]){
            pq.push(make_pair(0,make_pair(i,(i+1)%n)));
        }
        if(A[i]+A[(i+1)%n]==x){
            pq.push(make_pair(1,make_pair(i,(i+1)%n)));
        }
    }
    int ans = 0;
    while(!pq.empty()){
        pair<int,pii> ff = pq.top(); pq.pop(); 
        if(pos.count(ff.s.f)<=0 || pos.count(ff.s.s)<=0) continue;
        ans++;
        auto it1 = pos.find(ff.s.f);
        auto it2 = pos.find(ff.s.s);
        if(it1==pos.begin() || it2==pos.end()){
            //we are removing the ends 
            pos.erase(pos.find(ff.s.f));
            pos.erase(pos.find(ff.s.s));
            if(sz(pos)>1){
                it2 = pos.begin();
                it1 = pos.end(); it1--;
                if(A[*it1]==A[*it2]){
                    pq.push(make_pair(0,make_pair(*it1,*it2)));
                }
                if(A[*it1]+A[*it2]==x){
                    pq.push(make_pair(1,make_pair(*it1,*it2)));
                }
            }
        }
        else{
            it1--;
            it2++;
            if(A[*it1]==A[*it2]){
                pq.push(make_pair(0,make_pair(*it1,*it2)));
            }
            if(A[*it1]+A[*it2]==x){
                pq.push(make_pair(1,make_pair(*it1,*it2)));
            }
            pos.erase(pos.find(ff.s.f));
            pos.erase(pos.find(ff.s.s));
        }
    }

    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3584kb

input:

6 5
1 1 4 5 1 4

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3664kb

input:

10 5
1 2 5 2 1 2 3 4 8 4

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: -100
Time Limit Exceeded

input:

1 963837006
731841442

output:


result: