QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113760#6627. Line Town1kri#0 7ms21472kbC++14980b2023-06-19 10:48:212024-05-31 14:06:50

Judging History

你现在查看的是最新测评结果

  • [2024-05-31 14:06:50]
  • 评测
  • 测评结果:0
  • 用时:7ms
  • 内存:21472kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-19 10:48:21]
  • 提交

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%