QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#135915 | #2299. Heating Up | mojospy | WA | 722ms | 31076kb | C++14 | 1.5kb | 2023-08-06 15:31:30 | 2023-08-06 15:31:32 |
Judging History
answer
#include<iostream>
#include<functional>
#include<queue>
#include<unordered_set>
using namespace std;
const int N=5e5+3;
typedef long long int ll;
ll a[N];
int n;
class cmp{
public:
bool operator()(const int i,const int j)const{
return a[i]>a[j];
}
};
int deal(int id){
if(id==n) return 0;
else if(id<0) return n-1;
else return id;
}
bool isvaild(ll num){
for(int i=0;i<n;++i){
if(num>=a[i]){
priority_queue<int,vector<int>,cmp> q;
unordered_set<int> s;
//cout<<a[i]<<" ";
s.insert(i);
//s.insert(deal(i+1));
//s.insert(deal(i-1));
s.insert(deal(i+1));
s.insert(deal(i-1));
q.push(deal(i+1));
q.push(deal(i-1));
num+=a[i];
bool flag=true;
while(!q.empty()){
if(num<a[q.top()]){
flag=false;
break;
}
int cur=q.top();
q.pop();
//cout<<a[cur]<<" ";
num+=a[cur];
s.insert(cur);
if(s.find(deal(cur+1))==s.end()){
s.insert(deal(cur+1));
q.push(deal(cur+1));
}
if(s.find(deal(cur-1))==s.end()){
s.insert(deal(cur-1));
q.push(deal(cur-1));
}
}
//cout<<endl;
if(flag) return true;
}
}
return false;
}
int main(){
ll l=1e13+5,r=-1;
cin>>n;
for(int i=0;i<n;++i){
cin>>a[i];
l=min(l,a[i]);
r=max(r,a[i]);
}
while(l<=r){
ll mid=((r-l)>>1)+l;
if(mid==3){
l=mid+1;
continue;
}
if(isvaild(mid)){
r=mid-1;
}else{
l=mid+1;
}
}
cout<<l;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3508kb
input:
4 10 20 15 1
output:
9
result:
ok single line: '9'
Test #2:
score: -100
Wrong Answer
time: 722ms
memory: 31076kb
input:
500000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
4
result:
wrong answer 1st lines differ - expected: '1', found: '4'