QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#863348#9975. HitoshizukumyloveATRIWA 39ms5864kbC++201.6kb2025-01-19 16:08:342025-01-19 16:08:40

Judging History

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

  • [2025-01-19 16:08:40]
  • 评测
  • 测评结果:WA
  • 用时:39ms
  • 内存:5864kb
  • [2025-01-19 16:08:34]
  • 提交

answer

#include<bits/stdc++.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#define int long long
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define nl t[n].l
#define nr t[n].r
#define gcd __gcd
#define itn int
#define db long double
using namespace std;
const int maxn=4e6+50;
const int inf=1e18+10;
const int INF=2e18;
const int mod=998244353;
//const db eps=1e-8;
//const db pi=acos(-1.0);
#define pop_count __builtin_popcountll
struct node{
    int a,b,id;
}c[maxn];
int vis[maxn];
void solve(){
    int n;
    cin>>n;
    rep(i,1,3*n)
    {
        vis[i]=0;
        cin>>c[i].a>>c[i].b;
        c[i].id=i;
    }
    sort(c+1,c+1+3*n,[&](node a,node b){return a.a<b.a;});
    vector<array<int,3>> ans;
    int i=3*n,j=3*n;
    while(ans.size()<n)
    {
        while(vis[c[i].id]) i--;
        vis[c[i].id]++;
        while(j>=1&&(vis[c[j].id]||c[j].b<c[i].a))
        {
            j--;
        }
        int x=j;
        vis[c[j].id]++;
        while(j>=1&&(vis[c[j].id]||c[j].b<c[i].a))
        {
            j--;
        }
        int y=j;
        vis[c[j].id]++;
        if(j==0)
        {
            cout<<"No\n";
            return;
        }
        ans.push_back({c[i].id,c[x].id,c[y].id});
    }
    cout<<"Yes\n";
    for(auto x:ans)
    {
        cout<<x[0]<<' '<<x[1]<<' '<<x[2]<<'\n';
    }
}


signed main()
{
   ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int __=1;
   srand((time(0)));
   cin>>__;
  while(__--)
  {
       solve();
  }
    return 0;
}

详细

Test #1:

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

input:

2
2
1 2
2 2
2 3
3 5
4 4
4 5
1
1 1
1 1000000000
1000000000 1000000000

output:

Yes
6 5 4
3 2 1
No

result:

ok >_< (2 test cases)

Test #2:

score: 0
Accepted
time: 39ms
memory: 5860kb

input:

100000
1
164154503 167959139
178382610 336470888
12298535 642802746
1
165064830 773386884
353585658 396628655
792066242 971207868
1
1607946 2087506
21674839 46761498
9518201 16843338
1
262361007 691952768
190585553 787375312
637191526 693319712
1
41970708 45277106
197619816 762263554
308360206 40724...

output:

No
No
No
Yes
3 1 2
No
Yes
3 2 1
No
No
No
No
No
Yes
2 3 1
Yes
3 2 1
No
No
No
No
Yes
2 1 3
No
Yes
2 1 3
No
No
Yes
2 1 3
No
No
Yes
2 3 1
No
No
No
No
No
No
No
Yes
3 1 2
No
No
Yes
3 2 1
No
No
No
No
No
No
No
No
No
No
No
No
Yes
3 1 2
No
No
Yes
3 1 2
Yes
1 2 3
No
No
Yes
3 1 2
No
No
No
Yes
2 3 1
Yes
3 1 2
No...

result:

ok >_< (100000 test cases)

Test #3:

score: -100
Wrong Answer
time: 37ms
memory: 5864kb

input:

50000
2
36364670 641009859
15071436 75475634
20446080 476927808
357784519 503158867
206641725 322595515
268011721 645468307
2
247717926 939887597
808609669 973764525
496738491 710156469
463547010 860350786
757388873 784695957
29903136 208427221
2
26681139 67590963
458238185 475357775
80127817 135993...

output:

No
No
No
No
No
No
No
No
No
No
No
No
Yes
4 6 2
1 5 3
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
4 5 3
6 1 2
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
5 4 1
2 3 6
No
No
No
Yes
2 1 4
5 6 3
No
No
Yes
2 1 4
5 6 3
Yes
4 1 3
2 5 6
Yes
4 6 3
5 1 2
No
Yes
2 5 1
3 6 4
No
No
No
No
Yes
6 4 1
3 5 2
...

result:

wrong answer There is a valid answer, but participant did not find it. (test case 38)