QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#419040 | #6526. Canvas | SIGHT# | WA | 0ms | 16872kb | C++23 | 3.1kb | 2024-05-23 17:12:43 | 2024-05-23 17:12:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5e5+5;
struct Node{
ll l,x,r,y,index,ans,pos,pos1,flag;
friend bool operator < (Node a,Node b){
return a.ans < b.ans;
}
}act[maxn];
ll T,n,m,cnt[maxn],out[maxn],maxx[maxn];
int main() {
cin>>T;
while(T--){
queue<ll> q,temp,temp4;
map<ll,ll> mp;
ll l,x,r,y,t=0;
memset(out,0,sizeof(out));
memset(cnt,0,sizeof(cnt));
memset(maxx,0,sizeof(maxx));
scanf("%lld%lld",&n,&m);
// for(int i = 1;i <= m;i++) q.push(i);
for(int i = 1;i <= m;i++){
scanf("%lld%lld%lld%lld",&act[i].l,&act[i].x,&act[i].r,&act[i].y);
maxx[act[i].l] = max(maxx[act[i].l],act[i].x);
// cout<<" %%% l "<<maxx[act[i].l]<<endl;
maxx[act[i].r] = max(maxx[act[i].r],act[i].y);
// cout<<act[i].x <<" @@@ "<<act[i].y<<endl;
act[i].index = i;act[i].ans = act[i].x + act[i].y;
// cout<<" i = "<<i<<" "<<act[i].ans<<endl;
// cout<<" ans = "<<act[i].ans<<endl;
if(act[i].ans == 4){
mp[act[i].l] = -1;mp[act[i].r] = -1;
}
if(act[i].ans == 3){
// cout<<"$$$"<<endl;
if(act[i].x == 2){
act[i].pos = act[i].l;act[i].pos1=act[i].r;
// cout<<" i "<<act[i].pos<<" !! "<<act[i].pos1<<endl;
}
else act[i].pos = act[i].r,act[i].pos1=act[i].l;
}
}
// sort(act+1,act+1+m);
// for(int i = 1;i <= m;i++){
//// cout<<act[i].ans <<" !! ! "<<act[i].index<<endl;
// }
for(int i = 1;i <= m;i++){
if(act[i].ans == 2){
// cout<<" i = "<<i<<" "<<act[i].ans<<endl;
q.push(act[i].index);
}
}
for(int i = 1;i <= m;i++){
if(act[i].ans == 2){
continue;
}
else if(act[i].ans == 4) temp4.push(act[i].index);
else{
if(mp.count(act[i].pos)){
// cout<<" i = "<<i<<" "<<act[i].ans<<endl;
q.push(act[i].index);
}else{
temp.push(act[i].index);
}
}
}
// cout<<"@@@"<<endl;
// queue<ll> p;
// while(!q.empty()){
// p.push(q.front());
// cout<<q.front()<<" ";
// q.pop();
// }
// cout<<endl;
// q = p;
// cout<<"@@@"<<endl;
queue<ll> ttemp;
while(!temp.empty()){
ll qtemp = temp.front();
temp.pop();
// cout<<" !!! "<<qtemp<<" @@ "<<maxx[act[qtemp].pos1]<<endl;
if(mp.count(act[qtemp].pos1) == 0 && maxx[act[qtemp].pos1]==2){
q.push(qtemp);
}else if(mp.count(act[qtemp].pos1) == 1){
// cout<<" !!! "<<qtemp<<endl;
q.push(qtemp);
}else{
ttemp.push(qtemp);
}
}
while(!ttemp.empty()){
q.push(ttemp.front());ttemp.pop();
}
while(!temp4.empty()){
q.push(temp4.front());temp4.pop();
// cout<<"*"<;
}
while(!q.empty()){
ll pos = q.front();q.pop();
// cout<<" pos = "<<pos<<endl;
ll l = act[pos].l,r = act[pos].r,x = act[pos].x,y = act[pos].y;
// cout<<" pos: "<<pos<<" "<<l <<x<<r<<y<<endl;
out[l] = x;out[r] = y;
cnt[++t] = pos;
}
ll temp1 = 0;
for(int i = 1;i <= n;i++) temp1 += out[i];
cout<<temp1<<endl;
for(int i = 1;i <= m;i++){
cout<<cnt[i];
if(i != m) cout<<" ";
}
cout<<endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 16872kb
input:
2 4 4 1 1 2 2 3 2 4 1 1 2 3 2 2 1 4 1 4 2 3 2 4 1 1 2 3 1
output:
7 4 2 1 3 5 2 1
result:
ok Correct. (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 16572kb
input:
1 10 13 1 1 2 2 2 1 3 2 1 2 3 1 3 1 4 2 4 1 5 2 5 1 6 2 4 2 6 1 7 1 8 2 8 1 9 2 7 2 9 1 5 2 9 1 8 2 10 2 1 1 10 1
output:
16 13 8 1 2 3 4 5 6 7 9 10 11 12
result:
wrong answer Jury has better answer. Participant 16, jury 19 (test case 1)