QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#803120#9574. StripsKogenta2010RE 28ms3720kbC++141.9kb2024-12-07 16:05:112024-12-07 16:05:21

Judging History

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

  • [2024-12-07 16:05:21]
  • 评测
  • 测评结果:RE
  • 用时:28ms
  • 内存:3720kb
  • [2024-12-07 16:05:11]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct cell{
	int col;
	int pos;
	bool operator <(const cell &b){
		return pos<b.pos;
	}
}c[maxn];
int ans[maxn],adj[maxn];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n,m,k,w;
		cin>>n>>m>>k>>w;
		for(int i=1;i<=n;i++){
			cin>>c[i].pos;
			c[i].col=1;
		}
		for(int i=1;i<=m;i++){
			cin>>c[n+i].pos;
			c[n+i].col=2;
		}
		int adjustment=0,st=0,strip_cnt=0,strip_cnt_rec=0;
		sort(c+1,c+1+(n+m));
		c[n+m+1].pos=w+1;
		c[n+m+1].col=2;
		bool jd=1;
		for(int i=1;i<=n+m+1;i++){
			//cout<<"Starts at "<<st<<" now."<<endl;
			if(c[i].col==2){
				//cout<<"Adjustment:"<<adjustment<<endl;
				if(c[i].pos<=st-adjustment){//must be covered by a strip no matter what
					jd=0;
					break;
				}
				else if(c[i].pos<=st){
					//cout<<"Found!"<<endl;
					int accum=0;
					for(int j=strip_cnt;j>strip_cnt_rec;j--){
						//cout<<"Adjustting for strip No."<<j<<":"<<max(st-c[i].pos+1-accum,0)<<endl;
						ans[j]-=max(st-c[i].pos+1-accum,0);
						accum+=adj[j];
					}
				}
				adjustment=0;
				st=c[i].pos;
				strip_cnt_rec=strip_cnt;
			}
			else{
				if(c[i].pos-st<=0)continue;
				adjustment+=c[i].pos-1-st;
				/*if(adjustment>=k){
					//adjustment%=k;
					/*int accum=0;
					for(int j=strip_cnt;j>strip_cnt_rec;j--){
						cout<<"Adjustting for strip No."<<j<<":"<<max(st-c[i].pos+1-accum,0)<<endl;
						ans[j]-=max(st-c[i].pos+1-accum,0);
						accum+=adj[j];
					}
					strip_cnt_rec=strip_cnt;
					//st=ans[strip_cnt];
					//adjustment=c[i].pos-1-ans[strip_cnt];
				}*/
				ans[++strip_cnt]=c[i].pos;
				adj[strip_cnt]=c[i].pos-1-st;
				st=c[i].pos+k-1;
			}
		}
		if(!jd){
			cout<<-1<<endl;
		}
		else{
			cout<<strip_cnt<<endl;
			for(int i=1;i<=strip_cnt;i++){
				cout<<ans[i]<<" ";
			}
			cout<<endl;
		}
	}
	return 0;
}
/*
1
4 0 3 8
3 5 6 8
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3720kb

input:

4
5 2 3 16
7 11 2 9 14
13 5
3 2 4 11
6 10 2
1 11
2 1 2 6
1 5
3
2 1 2 6
1 5
2

output:

4
2 7 10 14 
-1
2
1 5 
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: 0
Accepted
time: 28ms
memory: 3624kb

input:

11000
3 8 2 53
32 3 33
35 19 38 20 1 30 10 6
7 10 1 42
3 14 4 36 28 40 22
17 20 12 41 27 7 1 19 13 9
6 6 13 78
55 76 53 32 54 58
62 45 21 4 7 61
8 7 3 68
9 26 54 31 22 3 38 65
34 16 58 47 52 29 53
5 8 4 33
33 5 30 6 15
27 12 9 28 19 2 13 10
6 1 2 48
8 12 48 1 41 31
40
7 6 7 61
20 19 30 52 49 17 40
3...

output:

2
3 32 
7
3 4 14 22 28 36 40 
3
32 48 66 
8
3 9 22 26 31 38 54 65 
3
5 15 30 
6
1 8 12 31 41 47 
4
17 30 39 49 
2
52 67 
1
27 
1
22 
1
62 
5
24 33 43 48 60 
2
4 31 
3
11 20 31 
3
3 16 33 
3
25 30 42 
3
3 17 60 
4
1 11 21 33 
2
54 66 
3
50 59 65 
3
50 62 78 
1
81 
4
2 11 16 23 
5
3 7 17 36 49 
2
1 45...

result:

ok ok 11000 cases (11000 test cases)

Test #3:

score: -100
Runtime Error

input:

2
62980 100000 9859 200000
132897 135912 27509 54599 183887 53114 127233 138596 120860 52471 83158 110644 114040 34102 100501 94779 188044 118947 57443 93009 179886 117863 142316 103026 133746 181956 88732 133751 178946 135462 99588 142382 116231 142902 98641 93039 34860 180746 34292 64655 31584 265...

output:


result: