QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#211106 | #6537. One, Two, Three | 275307894a | WA | 4ms | 19700kb | C++14 | 1.7kb | 2023-10-12 09:43:43 | 2023-10-12 09:43:44 |
Judging History
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