QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#211106#6537. One, Two, Three275307894aWA 4ms19700kbC++141.7kb2023-10-12 09:43:432023-10-12 09:43:44

Judging History

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

  • [2023-10-12 09:43:44]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:19700kb
  • [2023-10-12 09:43:43]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=6e5+5,M=N*4,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const ll INF=1e18+7;mt19937 rnd(263082);
int n,A[N];
vector<int> S[N];
struct Node{int x,y,z;};vector<Node> ans; 
void Solve(){
	int i,j;scanf("%d",&n);
	deque<int> s1,s3;
	for(i=1;i<=n;i++) scanf("%d",&A[i]);
	for(i=1;i<=n;i++) {
		if(A[i]==1) s1.emplace_back(i);
		if(A[i]==3) s3.emplace_back(i);
	}
	vector<int> p1,p2,q1,q2;
	while(!s1.empty()&&!s3.empty()){
		if(s1.front()<s3.front()) p1.emplace_back(s1.front()),p2.emplace_back(s3.back()),s1.pop_front(),s3.pop_back();
		else q1.emplace_back(s1.back()),q2.emplace_back(s3.front()),s1.pop_back(),s3.pop_front();
	}
	sort(p1.begin(),p1.end());sort(p2.begin(),p2.end());for(i=0;i<p1.size();i++) S[p1[i]].emplace_back(p2[i]);
	sort(q1.begin(),q1.end());sort(q2.begin(),q2.end());for(i=0;i<q1.size();i++) S[q2[i]].emplace_back(q1[i]);
	priority_queue<pii> q;
	for(i=1;i<=n;i++){
		for(int j:S[i]) q.emplace(-j,i);
		if(A[i]==2){
			while(!q.empty()&&-q.top().fi<i) q.pop();
			if(!q.empty()) ans.emplace_back((Node){q.top().se,i,-q.top().fi}),q.pop();
		}
	}
	printf("%d\n",ans.size());
	for(auto i:ans) printf("%d %d %d\n",i.x-1,i.y-1,i.z-1);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6
3 1 2 2 3 1

output:

2
1 2 4
0 3 5

result:

ok count=2

Test #2:

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

input:

6
2 1 3 1 3 2

output:

0

result:

ok count=0

Test #3:

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

input:

3000
1 1 1 1 1 3 1 1 3 3 1 3 1 1 2 3 1 1 2 1 2 1 3 3 3 1 1 2 1 2 2 3 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 3 3 1 1 2 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 2 1 1 1 2 3 1 1 1 1 3 3 2 1 3 1 1 2 3 1 2 3 1 1 1 2 1 1 1 1 2 3 2 1 1 1 1 1 2 1 1 1 1 1 1 1 2 1 1 1 3 1 3 3 1 1 1 1 3 1 1 2 1 1 1 3 3 1 1 1 1 2 1 1 1 1 1 2 3 3 1...

output:

499
0 14 604
1 18 607
2 20 616
3 27 624
4 29 627
6 30 639
7 39 651
10 46 661
12 51 673
13 54 681
16 60 687
17 67 697
19 71 699
21 79 704
25 84 706
26 87 714
28 92 727
32 97 728
33 99 730
34 105 735
35 113 736
36 128 740
37 138 743
38 144 744
40 148 747
41 162 750
42 167 754
43 168 755
44 176 758
45 ...

result:

ok count=499

Test #4:

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

input:

3000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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
0 1374 2901

result:

ok count=1

Test #5:

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

input:

3000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

1
1755 1756 2819

result:

ok count=1

Test #6:

score: -100
Wrong Answer
time: 3ms
memory: 18484kb

input:

1500
1 1 1 2 1 1 1 2 2 2 2 2 1 1 3 1 2 2 3 1 2 2 2 2 1 2 1 2 1 1 3 1 2 2 2 2 1 1 3 1 1 2 2 3 2 1 3 1 1 2 2 2 1 2 2 2 2 2 1 2 3 2 3 2 3 2 1 3 2 1 2 3 2 2 3 2 3 1 1 3 1 3 1 3 3 3 1 3 3 3 1 1 3 1 3 1 3 1 1 1 3 1 3 1 3 3 1 1 1 3 1 1 3 1 1 1 1 1 3 3 3 3 1 3 1 1 1 1 3 3 3 3 3 3 1 3 1 1 1 3 1 3 1 1 1 1 3 1...

output:

494
0 3 542
1 7 544
2 8 545
4 9 547
5 10 550
6 11 554
14 16 541
12 17 557
18 20 543
13 21 558
15 22 559
19 23 563
24 25 564
26 27 566
30 32 546
28 33 570
29 34 573
31 35 576
38 41 548
36 42 577
43 44 549
46 49 551
37 50 580
39 51 581
40 53 582
45 54 599
47 55 601
48 56 602
52 57 607
58 59 608
60 61 ...

result:

wrong answer the number of matches is different