QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#113779#6627. Line Town1kri#3 44ms32108kbC++142.3kb2023-06-19 11:39:492024-05-31 14:07:27

Judging History

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

  • [2024-05-31 14:07:27]
  • 评测
  • 测评结果:3
  • 用时:44ms
  • 内存:32108kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-19 11:39:49]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define inf 1000000000000ll
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{
		if (_abs(v)!=_abs(y.v))return _abs(v)<_abs(y.v);
		if (v!=y.v)return v<y.v;
		return p<y.p;
	}
}a[1000005];
struct BIT{
	int tree[1000005];
	void clear(){
		memset(tree,0,sizeof(tree));
		return;
	}
	void add(int p,int v){
		while(p<=n)tree[p]+=v,p+=(p&(-p));
		return;
	}
	int ask(int p){
		int ans=0;
		while(p)ans+=tree[p],p-=(p&(-p));
		return ans;
	}
}bit;
ll c[1000005][2];
ll f[1000005][2];
int t0[1000005],t1[1000005];
int pos[1000005];
ll ask(int len){
	ll ans=0;
	for (int i=1;i<=len;i++)
		if (pos[i]==0)return inf;
	for (int i=1;i<=len;i++){
		ans+=bit.ask(n)-bit.ask(pos[i]);
		bit.add(pos[i],1);
	}
	for (int i=1;i<=len;i++)bit.add(pos[i],-1);
	return ans;
}
int get_o(int o,int x){
	return ((x-1)&1)^o;
}
ll dfs(int now,int o){
	if (f[now][o]!=-1)return f[now][o];
	if (now==0)return 0;
	int l=now,r=now;
	while(l>1&&_abs(a[l-1].v)==_abs(a[r].v))l--;
	int l0=0,l1=0;
	for (int i=l;i<=r;i++)
		if (a[i].v<0)t0[++l0]=a[i].p;
		else t1[++l1]=a[i].p;
	int len=r-l+1;
	ll ans=inf;
	for (int i=0;i<=len;i++){
		int cnt0=0,cnt1=0;
		ll s=0;
		for (int j=1;j<=i;j++){
			if (get_o(o,j)==1)pos[j]=t0[++cnt0];
			else pos[j]=t1[++cnt1];
			s+=c[pos[j]][0];
		}
		for (int j=i+1;j<=len;j++){
			if (get_o(o,now-(len-j))==0)pos[j]=t0[++cnt0];
			else pos[j]=t1[++cnt1];
			s+=c[pos[j]][1];
		}
		if (cnt0==l0&&cnt1==l1)ans=min(ans,s+ask(len)+dfs(l-1,get_o(o,i+1)));
	}
	// if (cnt0==l0&&cnt1==l1)ans=min(ans,s+ask(len));
	// if (len&1){
	// 	for (int i=len;i>=1;i--)
	// 		if (cnt0==l0&&cnt1==l1)ans=min(ans,s+ask(len));
	// }
	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);
	int j=1;
	for (int i=1;i<=n;i++){
		while(_abs(a[j].v)<_abs(a[i].v))bit.add(a[j].p,1),j++;
		c[i][0]=bit.ask(a[i].p-1);
		c[i][1]=bit.ask(n)-bit.ask(a[i].p);
	}
	c[0][0]=c[0][1]=inf;
	bit.clear();
	memset(f,-1,sizeof(f));
	ll ans=dfs(n,0);
	if (ans==inf)ans=-1;
	cout<<ans<<endl;
	return 0;
}

详细

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 0ms
memory: 31988kb

input:

10
1 1 1 1 1 -1 -1 -1 1 -1

output:

-1

result:

ok 1 number(s): "-1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 30408kb

input:

10
1 1 1 1 1 1 -1 1 1 -1

output:

3

result:

ok 1 number(s): "3"

Test #3:

score: 0
Accepted
time: 0ms
memory: 27404kb

input:

1
-1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 42ms
memory: 30284kb

input:

2000
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 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 ...

output:

15146

result:

ok 1 number(s): "15146"

Test #5:

score: 0
Accepted
time: 43ms
memory: 30476kb

input:

2000
-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 1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 1 1 -1 1 1 -1 -1 -1 ...

output:

24933

result:

ok 1 number(s): "24933"

Test #6:

score: 0
Accepted
time: 44ms
memory: 30700kb

input:

2000
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 1 1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 1 -...

output:

18090

result:

ok 1 number(s): "18090"

Test #7:

score: 0
Accepted
time: 0ms
memory: 32108kb

input:

2000
-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 1 1 -1 -1 -1 1 -1 -1 1 -1 1 1 1 -1 1 -1 -1 1 1 1...

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

score: 0
Accepted
time: 43ms
memory: 29528kb

input:

2000
-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 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 ...

output:

9973

result:

ok 1 number(s): "9973"

Test #9:

score: 0
Accepted
time: 39ms
memory: 30724kb

input:

2000
-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 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #10:

score: 0
Accepted
time: 36ms
memory: 32064kb

input:

2000
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 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #11:

score: 0
Accepted
time: 40ms
memory: 31976kb

input:

1999
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 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

499500

result:

ok 1 number(s): "499500"

Test #12:

score: 0
Accepted
time: 35ms
memory: 31180kb

input:

1997
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 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

498501

result:

ok 1 number(s): "498501"

Test #13:

score: 0
Accepted
time: 4ms
memory: 30504kb

input:

2000
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 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 ...

output:

-1

result:

ok 1 number(s): "-1"

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #14:

score: 3
Accepted
time: 0ms
memory: 30076kb

input:

1
1

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: -3
Time Limit Exceeded

input:

500000
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 -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:


result:


Subtask #3:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #25:

score: 0
Wrong Answer
time: 0ms
memory: 31920kb

input:

10
0 1 0 0 1 1 -1 0 1 -1

output:

-1

result:

wrong answer 1st numbers differ - expected: '9', found: '-1'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #5:

score: 0
Wrong Answer

Test #60:

score: 4
Accepted
time: 4ms
memory: 30332kb

input:

10
3 10 5 -9 7 2 -6 1 8 0

output:

-1

result:

ok 1 number(s): "-1"

Test #61:

score: -4
Wrong Answer
time: 0ms
memory: 27328kb

input:

10
-9 0 -1 7 5 10 6 3 2 -8

output:

10

result:

wrong answer 1st numbers differ - expected: '13', found: '10'

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #3:

0%

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%