QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#652349#7942. $K$ SubsequencesaasWA 40ms5876kbC++14874b2024-10-18 18:36:302024-10-18 18:36:31

Judging History

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

  • [2024-10-18 18:36:31]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:5876kb
  • [2024-10-18 18:36:30]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<set>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e6+100;
int a[N],b[N];
int n,k;
set<pii> s;
void s1(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=k;i++)s.insert({0,i});
	if(k==1){
		int dp=0,ddp=0;
		for(int i=1;i<=n;i++)dp=max(0,dp+a[i]),ddp=max(dp,ddp);
		cout<<ddp<<endl;
	}
	for(int i=1;i<=n;i++){
		if(a[i]==1){
			auto it1=s.begin();
			pii cur=*it1;
			s.erase(cur);
			cur.fi=cur.fi+1;
			b[i]=cur.se;
			s.insert(cur);
		}	else{
			auto it1=(--s.end());
			pii cur=*it1;
			s.erase(cur);
			cur.fi=max(cur.fi-1,0);
			b[i]=cur.se;
			s.insert(cur);
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d ",b[i]);
	}
	puts("");
	s.clear();
}
int main(){
	int t;
	cin>>t;
	while(t--){
		s1();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5872kb

input:

5
3 2
1 -1 1
4 2
-1 1 1 -1
7 3
1 1 1 1 1 1 1
10 3
1 1 1 1 -1 -1 1 1 1 1
12 4
1 1 1 1 -1 -1 -1 -1 1 1 1 1

output:

1 1 1 
2 1 2 2 
1 2 3 1 2 3 1 
1 2 3 1 1 3 3 1 2 3 
1 2 3 4 4 3 2 1 1 2 3 4 

result:

ok Correct (5 test cases)

Test #2:

score: -100
Wrong Answer
time: 40ms
memory: 5876kb

input:

18434
10 1
-1 1 1 -1 -1 1 -1 -1 1 1
10 2
-1 -1 -1 1 1 -1 1 1 1 1
10 2
1 -1 -1 -1 -1 1 1 -1 1 1
10 7
1 1 -1 1 -1 1 1 -1 -1 1
9 1
-1 1 -1 1 1 -1 1 -1 1
8 1
-1 -1 -1 -1 1 1 -1 -1
10 3
-1 -1 -1 1 1 1 1 -1 -1 -1
9 1
1 -1 -1 1 -1 -1 -1 -1 -1
10 10
-1 1 1 1 1 1 1 1 1 1
10 4
-1 1 -1 1 -1 1 1 -1 1 1
9 3
1 1 ...

output:

2
1 1 1 1 1 1 1 1 1 1 
2 2 2 1 2 2 2 1 2 1 
1 1 2 2 2 1 2 2 2 1 
1 2 2 2 2 2 3 3 2 2 
2
1 1 1 1 1 1 1 1 1 
2
1 1 1 1 1 1 1 1 
3 3 3 1 2 3 1 1 3 2 
1
1 1 1 1 1 1 1 1 1 
10 1 2 3 4 5 6 7 8 9 
4 1 1 1 1 1 2 2 2 3 
1 2 2 1 1 1 1 1 3 
1 2 2 2 3 4 4 4 
7 1 2 3 4 5 6 7 7 7 
1 1 6 1 1 6 1 2 2 
5
1 1 1 1 1 1...

result:

wrong answer Integer element [index=1] equals to 2, violates the range [1, 1] (test case 1)