QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87719#4929. Longest Unfriendly Subsequencesnpmrnhlol0 142ms21296kbC++143.5kb2023-03-14 05:02:082023-03-14 05:02:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-14 05:02:09]
  • 评测
  • 测评结果：0
  • 用时：142ms
  • 内存：21296kb
查看
  • [2023-03-14 05:02:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int v[200000];
int pre[200000][6];
map <int,int> f;
pair <int,int> dp[200000][2];
///first - chosen bitch, second - maxxxxxx
void solve(){
    f.clear();
    int n,i,j,l,cnt = 0,ans = 0;
    cin>>n;
    for(i = 0;i < n;i++){
        cin>>v[i];
        f[v[i]] = 1;
        for(j = 0;j < 6;j++)pre[i][j] = -1;
        dp[i][0] = dp[i][1] = {0,-1};
    }
    for(auto &i:f){
        i.second = cnt++;
    }
    for(i = 0;i < n;i++){
        v[i] = f[v[i]];
        bool ok = 0;
        if(i)for(j = 0;j < 6;j++){
            if(pre[i - 1][j] == v[i]){
                ///same
                for(l = j + 1;l < 6;l++)pre[i][l] = pre[i - 1][l];
                for(l = j;l > 0;l--){
                    pre[i][l] = pre[i - 1][l - 1];
                }
                pre[i][0] = v[i];
                ok = 1;
            }
        }
        if(!ok){
            if(i)for(j = 6;j > 0;j--){
                pre[i][j] = pre[i - 1][j - 1];
            }
            pre[i][0] = v[i];
        }
    }
    for(i = 0;i < n;i++){
        int cur = 0,cand = -1,cur2 = 0,cand2 = -1;
        if(i)for(j = 0;j < 6;j++){
            if(pre[i - 1][j] == -1 || pre[i - 1][j] == v[i])continue;
            //cout<<pre[i - 1][j]<<' ';
            if(dp[pre[i - 1][j]][0].first != v[i] && dp[pre[i - 1][j]][0].second >= cur){
                cur = dp[pre[i - 1][j]][0].second;
                cand = pre[i - 1][j];
            }
            if(dp[pre[i - 1][j]][1].first != v[i] && dp[pre[i - 1][j]][1].second >= cur){
                cur = dp[pre[i - 1][j]][1].second;
                cand = pre[i - 1][j];
            }
        }
        if(i)for(j = 0;j < 6;j++){
            if(pre[i - 1][j] == -1 || pre[i - 1][j] == v[i] || pre[i - 1][j] == cand)continue;
            //cout<<pre[i - 1][j]<<' ';
            if(dp[pre[i - 1][j]][0].first != v[i] && dp[pre[i - 1][j]][0].second >= cur){
                cur2 = dp[pre[i - 1][j]][0].second;
                cand2 = pre[i - 1][j];
            }
            if(dp[pre[i - 1][j]][1].first != v[i] && dp[pre[i - 1][j]][1].second >= cur){
                cur2 = dp[pre[i - 1][j]][1].second;
                cand2 = pre[i - 1][j];
            }
        }
        cur2++;
        cur++;
        ans = max(ans,cur);
        ans = max(ans,cur2);
        //cout<<cur<<' '<<cand<<'\n';
        ///propagation
        if(dp[v[i]][0].first == cand){
            if(dp[v[i]][0].second <= cur){
                dp[v[i]][0].second = cur;
            }
        }else if(dp[v[i]][1].first == cand){
            if(dp[v[i]][1].second <= cur){
                dp[v[i]][1].second = cur;
            }
        }else if(dp[v[i]][0].second <= cur){
            dp[v[i]][1] = dp[v[i]][0];
            dp[v[i]][0] = {cand,cur};
        }else if(dp[v[i]][1].second <= cur){
            dp[v[i]][1] = {cand,cur};
        }
        if(dp[v[i]][0].first == cand2){
            if(dp[v[i]][0].second <= cur2){
                dp[v[i]][0].second = cur2;
            }
        }else if(dp[v[i]][1].first == cand2){
            if(dp[v[i]][1].second <= cur2){
                dp[v[i]][1].second = cur2;
            }
        }else if(dp[v[i]][0].second <= cur2){
            dp[v[i]][1] = dp[v[i]][0];
            dp[v[i]][0] = {cand2,cur2};
        }else if(dp[v[i]][1].second <= cur2){
            dp[v[i]][1] = {cand2,cur2};
        }
    }
    cout<<ans<<'\n';
}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
/**
1
8
1 2 1 3 2 1 3 3
**/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 3
Accepted
time: 67ms
memory: 11956kb

input:

1
200000
259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 259021863 2...

output:

1

result:

ok single line: '1'

Test #2:

score: -3
Wrong Answer
time: 142ms
memory: 21296kb

input:

1
200000
1521 1638 11981 18811 20091 22081 30494 31501 42139 42282 48197 55520 57632 69584 81745 85026 90303 91482 92176 98507 108061 108743 111257 121226 127217 127449 137116 163474 169192 175764 181243 185402 191244 198775 202845 212156 217723 220058 223478 224205 227614 228398 230425 232567 24480...

output:

198857

result:

wrong answer 1st lines differ - expected: '198858', found: '198857'

Subtask #2:

score: 0
Wrong Answer

Test #15:

score: 6
Accepted
time: 2ms
memory: 3516kb

input:

3
5
1 2 1 2 1
7
1 2 3 2 1 2 3
8
1 10 10 1 1 100 100 1

output:

2
6
4

result:

ok 3 lines

Test #16:

score: -6
Wrong Answer
time: 118ms
memory: 3472kb

input:

28653
6
372076545 832760265 372076545 644300403 644300403 644300403
8
540046638 375129642 863244619 863244619 375129642 540046638 540046638 540046638
6
142783193 508154499 871683432 71368434 871683432 871683432
8
760894385 984189193 760894385 323542350 984189193 760894385 323542350 323542350
6
84093...

output:

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

result:

wrong answer 43rd lines differ - expected: '5', found: '4'

Subtask #3:

score: 0
Wrong Answer

Test #19:

score: 8
Accepted
time: 2ms
memory: 3396kb

input:

1
500
537076440 691668159 871942500 537076440 537076440 691668159 871942500 871942500 537076440 691668159 871942500 537076440 691668159 871942500 537076440 691668159 871942500 537076440 691668159 871942500 537076440 691668159 871942500 871942500 537076440 691668159 871942500 537076440 537076440 6916...

output:

361

result:

ok single line: '361'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3380kb

input:

1
500
584142119 101442702 335815880 584142119 101442702 335815880 584142119 101442702 335815880 584142119 101442702 335815880 584142119 101442702 101442702 335815880 335815880 584142119 584142119 101442702 101442702 335815880 584142119 101442702 335815880 584142119 101442702 335815880 584142119 1014...

output:

394

result:

ok single line: '394'

Test #21:

score: -8
Wrong Answer
time: 0ms
memory: 3444kb

input:

1
500
296341737 806184542 989331127 989331127 296341737 806184542 455929030 296341737 806184542 806184542 806184542 989331127 296341737 806184542 989331127 296341737 806184542 989331127 296341737 806184542 989331127 296341737 806184542 806184542 989331127 296341737 296341737 296341737 806184542 9893...

output:

321

result:

wrong answer 1st lines differ - expected: '339', found: '321'

Subtask #4:

score: 0
Wrong Answer

Test #79:

score: 10
Accepted
time: 36ms
memory: 12032kb

input:

1
200000
1 3 3 2 2 3 3 1 2 3 1 1 3 3 3 2 1 1 2 3 2 1 3 3 3 1 2 2 1 3 1 2 1 2 3 2 3 3 2 2 3 2 3 2 3 1 1 1 1 1 3 1 3 2 3 3 3 3 1 3 2 1 3 2 3 2 3 1 1 1 1 3 3 2 3 2 1 2 2 3 2 3 2 2 2 2 2 2 3 2 1 2 2 1 1 3 2 1 2 1 1 3 3 3 2 1 2 2 2 1 3 3 2 3 2 1 3 3 2 2 1 3 1 3 2 1 2 3 2 1 2 3 2 2 3 2 1 2 1 1 1 1 1 1 1 3...

output:

66691

result:

ok single line: '66691'

Test #80:

score: 0
Accepted
time: 32ms
memory: 12052kb

input:

1
200000
2 2 3 3 3 2 1 2 1 1 1 3 3 2 3 3 1 3 2 3 3 3 2 1 2 2 2 2 1 1 2 2 1 3 1 3 1 3 3 1 2 1 1 2 1 1 2 1 1 1 1 2 2 1 3 2 3 3 2 3 2 3 1 1 1 1 2 3 1 2 1 1 2 3 2 3 3 2 1 2 1 1 3 3 3 1 2 3 1 3 1 3 1 1 2 1 3 2 1 1 3 2 1 1 3 2 3 2 3 2 1 3 2 2 2 1 2 2 1 3 3 1 3 1 2 3 1 1 2 2 2 1 3 1 1 3 3 2 3 2 1 3 1 1 1 3...

output:

66403

result:

ok single line: '66403'

Test #81:

score: -10
Wrong Answer
time: 21ms
memory: 12124kb

input:

1
200000
1 2 3 3 1 2 3 3 1 2 3 1 1 2 3 1 2 3 1 2 2 3 1 2 2 3 3 3 1 2 3 3 1 2 3 3 1 1 2 2 3 3 1 2 3 3 1 1 2 3 1 2 2 3 3 1 2 3 1 1 1 1 2 3 3 1 2 2 3 1 1 1 2 2 3 3 1 1 1 2 2 3 1 1 2 3 3 1 1 2 3 1 2 3 1 2 3 3 1 1 2 3 1 1 1 1 2 3 1 2 3 3 1 2 2 2 2 2 3 1 1 2 3 1 2 2 3 1 2 3 3 1 2 2 3 1 2 3 1 1 1 2 2 3 1 2...

output:

100295

result:

wrong answer 1st lines differ - expected: '113082', found: '100295'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #3:

0%

Subtask #7:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-02 15:45:27 | OpenSource Project