QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#128551 | #6718. Масив i частковi суми | Random_Code | 14 | 12ms | 7004kb | C++14 | 2.0kb | 2023-07-21 10:36:37 | 2023-07-21 10:36:40 |
Judging History
answer
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 998244353
#define F first
#define S second
#define ll long long
#define N 200010
using namespace std;
ll n,a[N],s[N];
vector<pair<ll,pair<ll,ll> > > ans;
bool check1()
{
ll i;
s[0]=0;
for(i=0;i<n;i++)
{
s[i+1]=s[i]+a[i];
if(s[i+1]<0)
{
return false;
}
}
ans.push_back(make_pair(2,make_pair(0,n-1)));
return true;
}
//bool check2()
//{
// ll i;
//}
bool check3()
{
ll i,mnp=0,mxp=0;
s[0]=0;
for(i=0;i<n;i++)
{
s[i+1]=s[i]+a[i];
if(s[i+1]<s[mnp])
{
mnp=i+1;
}
if(s[i+1]>s[mxp])
{
mxp=i+1;
}
}
if(mnp>mxp)
{
ans.push_back(make_pair(1,make_pair(0,0)));
}
mnp=mxp=0;
s[0]=0;
for(i=0;i<n;i++)
{
s[i+1]=s[i]+a[i];
if(s[i+1]<s[mnp])
{
mnp=i+1;
}
if(s[i+1]>s[mxp])
{
mxp=i+1;
}
}
if(mnp<n)
{
ans.push_back(make_pair(2,make_pair(mnp,n-1)));
}
ans.push_back(make_pair(3,make_pair(0,n-1)));
return true;
}
void print(ll tp)
{
ll i;
printf("%d\n",ans.size());
for(i=0;i<ans.size();i++)
{
if(ans[i].F==1)
{
puts("1");
}
else if(!tp)
{
printf("%lld %lld %lld\n",ans[i].F,ans[i].S.F+1,ans[i].S.S+1);
}
else
{
printf("%lld %lld %lld\n",ans[i].F^1,n-ans[i].S.S,n-ans[i].S.F);
}
}
return;
}
int main(){
// freopen("draftpaper.in","r",stdin);
// freopen("draftpaper.out","w",stdout);
ll T,i,mx=0,mn=0;
scanf("%lld%lld",&n,&T);
for(i=0;i<n;i++)
{
scanf("%lld",&a[i]);
mx=max(mx,a[i]);
mn=min(mn,a[i]);
}
if(mn>=0)
{
puts("0");
return 0;
}
if(mx<=0)
{
puts("1");
puts("1");
return 0;
}
if(check1())
{
print(0);
return 0;
}
reverse(a,a+n);
if(check1())
{
print(1);
return 0;
}
// reverse(a,a+n);
// if(check2())
// {
// print(0);
// return 0;
// }
// reverse(a,a+n);
// if(check2())
// {
// print(1);
// return 0;
// }
// reverse(a,a+n);
assert(check3());
print(0);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 14
Accepted
Test #1:
score: 14
Accepted
time: 9ms
memory: 5284kb
input:
200000 1 1 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 0 0...
output:
0
result:
ok OK: 0 operations
Test #2:
score: 0
Accepted
time: 11ms
memory: 6000kb
input:
200000 1 -1 0 0 0 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 0 -1 -1 0 0 0 -1 -1 0 -1 0 -1 0 -1 0 -1 -1 0 0 -1 -1 0 0 -1 -1 0 -1 -1 -1 -1 0 -1 -1 0 0 0 -1 0 -1 -1 -1 0 -1 -1 0 0 0 -1 -1 -1 -1 -1 0 0 -1 -1 0 -1 0 -1 0 -1 -1 -1 0 -1 -1 0 0 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 -...
output:
1 1
result:
ok OK: 1 operations
Test #3:
score: 0
Accepted
time: 12ms
memory: 7004kb
input:
200000 1 0 0 1 -1 1 1 -1 -1 0 1 -1 0 0 1 0 0 1 1 1 1 0 -1 -1 0 -1 -1 1 -1 1 1 1 1 -1 1 -1 1 1 0 -1 -1 0 1 0 0 0 0 1 1 -1 0 0 -1 -1 -1 0 0 0 1 1 1 -1 1 1 0 0 1 1 -1 1 0 0 1 1 1 1 -1 0 1 0 0 0 0 1 0 0 -1 0 -1 1 -1 0 1 -1 -1 0 0 0 -1 0 0 1 1 1 0 -1 0 1 1 1 0 1 0 0 0 -1 -1 0 -1 -1 1 -1 -1 1 1 0 1 1 1 -1...
output:
1 2 1 200000
result:
ok OK: 1 operations
Test #4:
score: 0
Accepted
time: 10ms
memory: 7004kb
input:
200000 1 -1 -1 -1 -1 0 1 0 -1 -1 0 -1 -1 1 0 0 -1 0 1 -1 0 -1 1 -1 0 1 1 0 1 1 1 0 0 1 -1 0 1 0 0 0 0 1 1 1 1 1 0 1 -1 1 1 0 -1 0 1 0 0 0 1 1 0 1 0 -1 -1 0 0 -1 -1 0 1 -1 -1 -1 0 1 0 0 -1 0 1 0 1 1 1 1 0 1 -1 -1 -1 0 0 0 -1 1 1 -1 -1 -1 1 0 0 -1 -1 0 -1 -1 -1 0 1 1 1 1 0 1 -1 -1 0 -1 0 0 0 -1 -1 -1 ...
output:
1 3 1 200000
result:
ok OK: 1 operations
Subtask #2:
score: 0
Wrong Answer
Test #5:
score: 17
Accepted
time: 11ms
memory: 5648kb
input:
200000 2 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0...
output:
0
result:
ok OK: 0 operations
Test #6:
score: 0
Accepted
time: 8ms
memory: 6364kb
input:
200000 2 0 0 -1 -1 0 -1 0 0 -1 -1 0 -1 -1 0 -1 0 -1 -1 -1 -1 -1 0 0 -1 0 -1 -1 0 0 -1 -1 -1 -1 -1 -1 -1 -1 0 0 -1 -1 0 -1 -1 -1 0 -1 0 -1 0 -1 0 0 0 0 0 0 0 0 0 0 -1 0 -1 0 -1 0 0 0 -1 -1 0 0 -1 -1 -1 0 -1 -1 0 -1 -1 -1 -1 0 -1 -1 -1 0 0 -1 0 0 0 -1 -1 -1 0 0 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 0 0 0 -1 -1...
output:
1 1
result:
ok OK: 1 operations
Test #7:
score: 0
Accepted
time: 12ms
memory: 6776kb
input:
200000 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
3 1 2 189971 200000 3 1 200000
result:
ok OK: 3 operations
Test #8:
score: -17
Wrong Answer
time: 12ms
memory: 6724kb
input:
200000 2 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
3 1 2 200000 200000 3 1 200000
result:
wrong answer Invalid sequence of operations
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #28:
score: 0
Wrong Answer
time: 1ms
memory: 3888kb
input:
2891 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 ...
output:
3 1 2 2823 2891 3 1 2891
result:
wrong answer Too many operations
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #5:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%