QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#758062#9730. Elevator IIruoye123456#WA 44ms5916kbC++202.3kb2024-11-17 15:27:072024-11-17 15:27:07

Judging History

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

  • [2024-11-17 15:27:07]
  • 评测
  • 测评结果:WA
  • 用时:44ms
  • 内存:5916kb
  • [2024-11-17 15:27:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}
const int N = 100005;
int l[N],r[N],id[N],mr[N],mrpos[N];
bitset<N> vis;
int n; 
struct INTERVAL{
    int l,r,id;
    // bool operator<(auto a){return l<a.l;}
}p[N];
void solve()
{
    int f;
    cin>>n>>f;
    ll sum = 0;
    vector<int> ans;
    for(int i=1;i<=n;++i)
    {
        cin>>p[i].l>>p[i].r;
        p[i].id = i;
        vis[i] = 0;
        sum += p[i].r-p[i].l;
    }
    // cout<<"111:"<<sum<<'\n';
    sort(p+1, p+n+1, [](auto a,auto b){return a.l<b.l;});
    for(int i=1;i<=n;++i)
    {
        l[i] = p[i].l;
        r[i] = p[i].r;
        id[i] = p[i].id;
        if(r[i] > mr[i-1]) {mrpos[i]=i; mr[i]=r[i];}
        else mr[i]=mr[i-1], mrpos[i]=mrpos[i-1];
        // cout<<"mr "<<mr[i]<<' '<<mrpos[i]<<'\n';
    }
    int now = upper_bound(l+1, l+n+1, f)-l-1;
    // cout<<now<<' ';
    while(now < n)
    {
        while(mr[now] >= l[now+1] && now < n) 
        {
            vis[mrpos[now]] = 1;
            ans.push_back(id[mrpos[now]]);
            f = mr[now];
            now = upper_bound(l+1, l+n+1, f)-l-1;
        }
        if(now == n) break;
        // cout<<now<<' '<<f<<'\n';
        sum += l[now+1] - f;
        f = l[now+1];
        ++now;
    }

    vector<INTERVAL> tmp;
    for(int i=1;i<=n;++i)
    {
        if(!vis[i]) tmp.push_back(p[i]);
    }
    sort(tmp.begin(), tmp.end(), [](auto a,auto b){return a.r>b.r;});

    cout<<sum<<'\n';
    for(auto &&e:ans) cout<<e<<' ';
    for(auto &&e:tmp) cout<<e.id<<' ';
    cout<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5916kb

input:

2
4 2
3 6
1 3
2 7
5 6
2 5
2 4
6 8

output:

11
3 1 4 2 
5
2 1 

result:

ok ok 2 cases (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 44ms
memory: 5692kb

input:

6100
19 52
51 98
2 83
40 58
96 99
39 55
72 94
15 17
4 15
48 99
2 99
77 78
35 77
44 62
79 81
30 31
1 48
48 76
68 99
60 66
6 19
44 53
64 92
17 28
67 98
9 99
40 65
16 27
99 100
15 56
4 6
24 97
84 96
47 49
37 38
77 79
13 40
13 92
71 100
47 93
90 91
72 81
15 48
32 71
19 17
95 99
10 23
18 100
90 93
52 92
...

output:

524
10 9 4 18 1 6 2 14 11 12 17 19 13 3 5 16 15 7 8 
194
5 4 2 6 1 3 
397
4 11 1 5 12 10 13 14 8 16 2 6 15 9 7 3 
733
7 3 1 10 6 8 4 17 5 16 13 11 15 12 18 14 9 19 2 
244
3 2 8 6 5 12 4 14 10 11 9 1 15 13 7 
422
18 1 6 11 10 2 7 13 9 12 4 20 14 5 15 8 19 16 3 17 
104
4 1 3 2 
187
4 8 3 1 2 6 7 5 9 1...

result:

wrong answer Participant's cost is 117, which is worse than jury's cost 92 (test case 10)