QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#239648	#7729. Permutation Compression II	Kanata	WA	89ms	5644kb	C++14	1.3kb	2023-11-04 22:10:42	2023-11-04 22:10:42

Judging History

This is the latest submission verdict.

[2023-11-04 22:10:42]
Judged

Verdict: WA
Time: 89ms
Memory: 5644kb

Show

[2023-11-04 22:10:42]
Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using ld = long double;
constexpr i64 N = 1e6;
i64 a[N + 10];
bool vis[N + 10];
void solve()
{
    i64 n;
    cin >> n;
    for (i64 i = 1; i <= n; i++)
    {
        vis[i] = 0;
    }
    vector<i64> tmp;
    for (i64 i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (tmp.empty() || tmp.back() < a[i])
        {
            tmp.push_back(a[i]);
            vis[a[i]] = 1;
        }
        else
        {
            i64 l = 0, r = tmp.size() - 1;
            while (l < r)
            {
                i64 mid = (l + r) >> 1;
                if (tmp[mid] > a[i])
                {
                    r = mid;
                }
                else
                {
                    l = mid + 1;
                }
            }
            vis[tmp[l]] = 0;
            tmp[l] = a[i];
            vis[a[i]] = 1;
        }
    }
    cout << tmp.size() << " "<<n-tmp.size()<<"\n";
    for (i64 i = 1; i <= n; i++)
    {
        if (!vis[a[i]])
        {
            cout << i << " ";
        }
    }
    cout << "\n";
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    i64 T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5572kb

input:

output:

2 1
1 
3 0

result:

ok ok n = 3

Test #2:

score: -100

Wrong Answer

time: 89ms

memory: 5644kb

input:

100000
7
2 6 7 1 4 3 5
6
1 5 6 3 2 4
3
1 2 3
3
2 1 3
14
9 6 13 10 4 7 5 14 1 12 8 3 2 11
3
1 2 3
14
1 9 3 14 5 7 4 6 12 2 8 11 13 10
8
7 1 3 6 2 5 8 4
16
9 3 4 8 7 16 10 6 11 1 14 2 13 12 5 15
3
3 1 2
33
9 10 23 3 16 1 19 32 25 4 5 31 28 7 22 27 30 8 6 17 2 14 13 29 20 33 26 18 24 11 12 15 21
2
2 1
...

output:

3 4
1 2 3 5 
3 3
2 3 4 
3 0

2 1
1 
4 10
1 2 3 4 5 6 7 8 10 12 
3 0

7 7
2 3 4 5 6 9 12 
4 4
1 3 4 6 
7 9
1 2 3 4 5 6 8 11 13 
2 1
1 
9 24
1 2 3 4 5 7 8 9 10 12 13 14 15 16 17 20 22 23 24 25 26 27 28 29 
1 1
1 
2 1
1 
1 0

2 2
1 2 
5 9
1 2 3 4 5 6 7 8 9 
2 3
1 2 3 
6 10
1 2 3 4 5 7 8 11 12 13 
3 1
1...

result:

wrong answer Jury has better answer