QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113760 | #6627. Line Town | 1kri# | 0 | 7ms | 21472kb | C++14 | 980b | 2023-06-19 10:48:21 | 2024-05-31 14:06:50 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define inf 1000000000000000000ll
using namespace std;
int n;
int _abs(int x){
if (x<0)return -x;
return x;
}
struct node{
int p,v;
bool operator <(const node &y)const{
return _abs(v)<_abs(y.v);
}
}a[1000005];
ll f[1000005][2];
ll dfs(int now,int o){
if (f[now][o]!=-1)return f[now][o];
if (now<=1)return 0;
int c0=0,c1=0;
for (int i=1;i<now;i++)
if (a[i].p>a[now].p)c0++;
else c1++;
int f0=1,f1=1;
if (o==1)f0=-1;
if (((now&1)^1^o)==1)f1=-1;
ll ans=inf;
if (a[now].v*f0<=0)ans=min(ans,c0+dfs(now-1,(o^1)));
if (a[now].v*f1>=0)ans=min(ans,c1+dfs(now-1,o));
return f[now][o]=ans;
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
a[i].p=i;
scanf("%d",&a[i].v);
if (i&1)a[i].v=-a[i].v;
}
sort(a+1,a+1+n);
memset(f,-1,sizeof(f));
ll ans=dfs(n,1);
if (ans==inf)ans=-1;
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 2ms
memory: 19564kb
input:
10 1 1 1 1 1 -1 -1 -1 1 -1
output:
-1
result:
ok 1 number(s): "-1"
Test #2:
score: -3
Wrong Answer
time: 0ms
memory: 21332kb
input:
10 1 1 1 1 1 1 -1 1 1 -1
output:
-1
result:
wrong answer 1st numbers differ - expected: '3', found: '-1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Wrong Answer
Test #60:
score: 4
Accepted
time: 0ms
memory: 21224kb
input:
10 3 10 5 -9 7 2 -6 1 8 0
output:
-1
result:
ok 1 number(s): "-1"
Test #61:
score: 0
Accepted
time: 4ms
memory: 20792kb
input:
10 -9 0 -1 7 5 10 6 3 2 -8
output:
13
result:
ok 1 number(s): "13"
Test #62:
score: 0
Accepted
time: 0ms
memory: 19420kb
input:
2000 40667 -598150 -1084780 1201651 1570514 -1859539 -2029075 2941581 -2945945 3038404 3447919 5293872 -5335692 -5669647 5973784 6041345 6346915 -7222112 8820986 -9153143 9563103 9749206 -9894732 -11847193 11987150 12161864 13336572 13528051 -13722732 -13836176 -15497141 -15841563 15862227 16618123 ...
output:
-1
result:
ok 1 number(s): "-1"
Test #63:
score: 0
Accepted
time: 5ms
memory: 21472kb
input:
2000 3038404 -798315545 693574695 172661079 516504064 164016456 193562146 -131746730 382134316 -398886978 188767854 -834289064 -965673210 -826409444 -281381674 450991903 -592752625 81651101 -594873306 -352059270 -651772982 540062674 -769881300 68999588 307151563 -129950325 550154987 354801227 840540...
output:
658039
result:
ok 1 number(s): "658039"
Test #64:
score: 0
Accepted
time: 7ms
memory: 20364kb
input:
2000 -1095 -925 -1049 -1519 951 -1673 -776 345 -38 -1735 -276 -1730 123 -1629 -1896 -1576 -1115 1145 15 797 -948 287 1487 1195 1269 -1240 -1571 -275 -1915 -369 -1221 -1590 -1392 -100 1688 -1287 -241 1130 -1375 -965 669 -147 -307 -795 -1207 1939 120 -305 -915 -1078 -1448 1458 -603 1935 658 774 1471 7...
output:
668545
result:
ok 1 number(s): "668545"
Test #65:
score: 0
Accepted
time: 7ms
memory: 20872kb
input:
2000 1290 1487 -1947 -255 457 -1202 1313 36 -1511 898 1739 987 1809 -1986 -1015 -1127 -703 -223 179 557 199 349 1099 -259 -1401 -1244 -1116 646 -295 1713 1512 127 -1660 343 -1921 -1326 -549 831 1963 -1743 1655 -698 1792 366 1517 -51 404 -1853 -1295 1652 -130 -1562 -1850 -582 1504 1888 822 -24 1807 9...
output:
663841
result:
ok 1 number(s): "663841"
Test #66:
score: 0
Accepted
time: 5ms
memory: 20028kb
input:
2000 56 -1667 -1636 -671 -1311 348 976 1381 -710 -477 -1301 756 -510 495 -1215 -278 1134 950 59 1739 -33 -839 -862 605 761 827 -1708 -1180 -607 1624 -120 -1198 624 -1237 -1874 1788 1005 -331 1266 -467 -1213 1736 -182 594 775 1209 -832 300 1188 -994 -191 -217 1360 -1907 71 436 1294 -590 913 -747 -629...
output:
667052
result:
ok 1 number(s): "667052"
Test #67:
score: -4
Wrong Answer
time: 6ms
memory: 20300kb
input:
1999 -758656 -113741 -374719 7680 -227905 -201318 -200890 -84484 777096 -167712 -126972 -244117 835074 161027 923025 -224756 973701 36622 -913757 -920737 -976062 461264 147694 -162457 358437 -308202 385370 808271 -523703 -303454 -522131 -664739 -505124 306509 948216 948694 -467953 -768055 769796 486...
output:
676771
result:
wrong answer 1st numbers differ - expected: '675957', found: '676771'
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%