QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#72130 | #4803. Candies | ricky0129 | WA | 72ms | 9488kb | C++14 | 2.1kb | 2023-01-14 12:41:57 | 2023-01-14 12:42:01 |
Judging History
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]);
if(n==1){
cout<<0<<endl;
return 0;
}
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: 3660kb
input:
10 5 1 2 5 2 1 2 3 4 8 4
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
1 963837006 731841442
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
2 948507270 461613425 139535653
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 30ms
memory: 9088kb
input:
100000 253614967 278270961 980235896 498158919 928430171 216003120 852570559 948400591 239257297 897053668 294741177 38297442 382677591 406314558 609468974 854148233 314532768 738191552 158215003 5865826 920471827 380037059 356271729 749175328 28319050 208101106 953758996 896570759 521930645 2413736...
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: -100
Wrong Answer
time: 72ms
memory: 9488kb
input:
100000 2 1 2 2 2 2 1 1 2 1 1 1 1 1 1 1 1 1 1 2 2 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 2 1 2 1 1 1 2 2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1 2 1 2 1 1 2 1 1 2 1 1 2 2 2 2 1 2 2 2 1 1 2 1 2 1 2 2 2 1 1 1 2 1 1 1 1 1 1 1 2 1 2 1 1 2 1 2 1 2 1 2 1 2 2 1 1 2 2 2 1 1 2 1 1 2 2 2 2 2 2 2 1 2 1 1 2 2 1 1 2 1 1 1 1...
output:
49971
result:
wrong answer 1st numbers differ - expected: '49999', found: '49971'