QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#719576#515. A Random Problemkevinyang#AC ✓3003ms585304kbC++202.9kb2024-11-07 04:01:402024-11-07 04:01:41

Judging History

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

  • [2024-11-07 04:01:41]
  • 评测
  • 测评结果:AC
  • 用时:3003ms
  • 内存:585304kb
  • [2024-11-07 04:01:40]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for (int i=a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


char d1[10][10][1005][1005];
char d2[10][10][1005][1005];
char d3[10][10][1005][1005];
char c1[10][10][1005][1005];
char c2[10][10][1005][1005];
char c3[10][10][1005][1005];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int p;
    cin >> p;
    vector<int>a(p+1);
    for(int i = 1; i<=p; i++){
        cin >> a[i];
    }
    int rq = (p+39)/40 + 1;
    for(int i = 1; i<=p; i++){
        for(int j = i+1; j<=p; j++){
            for(int k = j+1; k<=p; k++){
                {
                    if(!d1[a[i]][a[j]][j-i][k-j]){
                        d1[a[i]][a[j]][j-i][k-j] = a[k]+'0';
                    }
                    else if(d1[a[i]][a[j]][j-i][k-j] != a[k] + '0'){
                        d1[a[i]][a[j]][j-i][k-j] = 1;
                    }
                    c1[a[i]][a[j]][j-i][k-j]++;
                    c1[a[i]][a[j]][j-i][k-j] = min(c1[a[i]][a[j]][j-i][k-j],(char)30);
                }
                {
                    if(!d2[a[i]][a[k]][j-i][k-j]){
                        d2[a[i]][a[k]][j-i][k-j] = a[j]+'0';
                    }
                    else if(d2[a[i]][a[k]][j-i][k-j] != a[j] + '0'){
                        d2[a[i]][a[k]][j-i][k-j] = 1;
                    }
                    c2[a[i]][a[k]][j-i][k-j]++;
                    c2[a[i]][a[k]][j-i][k-j] = min(c2[a[i]][a[k]][j-i][k-j],(char)30);
                }
                {
                    if(!d3[a[j]][a[k]][j-i][k-j]){
                        d3[a[j]][a[k]][j-i][k-j] = a[i]+'0';
                    }
                    else if(d3[a[j]][a[k]][j-i][k-j] != a[i] + '0'){
                        d3[a[j]][a[k]][j-i][k-j] = 1;
                    }
                    c3[a[j]][a[k]][j-i][k-j]++;
                    c3[a[j]][a[k]][j-i][k-j] = min(c3[a[j]][a[k]][j-i][k-j],(char)30);
                }
                
            }
        }
    }
    for(int i = 1; i<=p; i++){
        for(int j = i+1; j<=p; j++){
            for(int k = j+1; k<=p; k++){
                if(d1[a[i]][a[j]][j-i][k-j] == a[k]+'0' && d2[a[i]][a[k]][j-i][k-j] == a[j] + '0' && d3[a[j]][a[k]][j-i][k-j] == a[i] + '0'){
                    int cnt1 = c1[a[i]][a[j]][j-i][k-j];
                    int cnt2 = c2[a[i]][a[k]][j-i][k-j];
                    int cnt3 = c3[a[j]][a[k]][j-i][k-j];
                    if(cnt1 == cnt2 && cnt2 == cnt3 && cnt1 >= rq){
                        cout << "triple correlation " << a[i] << "(" << j-i << ")" << a[j] << "(" << k-j << ")" << a[k] << " found\n";
                        return 0;
                    }
                }
            }
        }
    }
    cout << "random sequence\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 143116kb

input:

100
4 7 9 5 9 3 5 0 0 1 7 8 5 0 2 6 3 5 4 4
4 6 3 3 2 7 1 8 7 8 7 6 1 1 7 2 5 4 7 2
0 4 4 5 8 3 0 6 9 3 2 6 6 8 5 2 5 1 2 7
2 4 1 0 0 4 9 1 8 7 5 0 4 4 8 4 3 2 6 8
8 5 6 7 0 9 7 0 3 6 1 4 4 1 2 3 2 6 9 9

output:

triple correlation 4(1)4(3)3 found

result:

ok single line: 'triple correlation 4(1)4(3)3 found'

Test #2:

score: 0
Accepted
time: 0ms
memory: 16516kb

input:

10
1 2 3 1 2 2 1 1 3 0

output:

random sequence

result:

ok single line: 'random sequence'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

1
0

output:

random sequence

result:

ok single line: 'random sequence'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

2
0 1

output:

random sequence

result:

ok single line: 'random sequence'

Test #5:

score: 0
Accepted
time: 0ms
memory: 87276kb

input:

30
8 7 4 2 5
2 5 7 2 5
8 2 3 2 3
5 4 9 5 9
6 1 6 1 1
4 1 0 5 0

output:

triple correlation 8(3)2(15)5 found

result:

ok single line: 'triple correlation 8(3)2(15)5 found'

Test #6:

score: 0
Accepted
time: 4ms
memory: 106496kb

input:

30
3
0
1
6
0
7
9
3
9
2
1
4
4
9
2
6
8
5
5
5
5
8
2
3
0
3
0
2
1
3

output:

triple correlation 9(11)5(6)3 found

result:

ok single line: 'triple correlation 9(11)5(6)3 found'

Test #7:

score: 0
Accepted
time: 0ms
memory: 99340kb

input:

30
6 6 3 9 4 9 2 2 6 7 1 1 7 8 8 5 4 4 5 3 3 6 3 6 9 0 6 9 0 9

output:

triple correlation 6(6)2(4)1 found

result:

ok single line: 'triple correlation 6(6)2(4)1 found'

Test #8:

score: 0
Accepted
time: 0ms
memory: 109732kb

input:

50
7 7 3 7 1 6 2 3 2 6 3 6 3 4 4 6 4 4 4 7 4 9 9 1 9
1 7 3 0 0 0 8 8 8 5 5 5 2 3 7 1 6 1 7 2 1 7 7 7 6

output:

triple correlation 7(13)4(4)4 found

result:

ok single line: 'triple correlation 7(13)4(4)4 found'

Test #9:

score: 0
Accepted
time: 0ms
memory: 112488kb

input:

50
0 5 2 1 3
0 0 5 0 1 5 1 2 3 7
7 1 6 6 8 8 7 5 5 6 0 8 4 0 4
1 2 9 4 3 4 0 1 9 1 4 1 4 2 1 9 2 0 0 1

output:

triple correlation 1(26)4(3)9 found

result:

ok single line: 'triple correlation 1(26)4(3)9 found'

Test #10:

score: 0
Accepted
time: 0ms
memory: 115432kb

input:

50
0 3 6 2 3 0 0 9 6 6
2 5 5 7 7
0 6 4 4 0 2 5 2 7 2 1 1 4 8 8 6
1 8 8 8 3 2 9 8 2 9 0 2 9 6 6 9 3 0
9

output:

triple correlation 0(6)5(2)7 found

result:

ok single line: 'triple correlation 0(6)5(2)7 found'

Test #11:

score: 0
Accepted
time: 3ms
memory: 106352kb

input:

50
1 3 3 1 1 4 3 4 3 2 4 3 1 5 5 5 1 7 7 7
4 9 9 9 1 3 1 3 4 1 4 6 6 6 8 8 8 0 0 0
3 4 1 3 4 2 3 2 1 1

output:

triple correlation 5(4)7(4)9 found

result:

ok single line: 'triple correlation 5(4)7(4)9 found'

Test #12:

score: 0
Accepted
time: 3ms
memory: 115436kb

input:

50
8 7 5 4 4 4 7 9 9 9 9 4 2 2 5 9 4 9 8 7 2 4 8 5 1 0 3 0 0 8 4 6 1 4 3 4 1 8 3 6 4 7 7 6 5 4 4 5 0 0

output:

triple correlation 4(6)9(3)2 found

result:

ok single line: 'triple correlation 4(6)9(3)2 found'

Test #13:

score: 0
Accepted
time: 0ms
memory: 114556kb

input:

41
5 2 6 7 9 4 8 1 5 3 3 2 2 6 5 1 1 3 8 8
7 1 4 3 8 0 6 7 7 7 1 4 9 2 3 9 2 9 8 6 1

output:

triple correlation 5(7)1(2)3 found

result:

ok single line: 'triple correlation 5(7)1(2)3 found'

Test #14:

score: 0
Accepted
time: 0ms
memory: 112440kb

input:

41
5 2 6 7 9 4 8 1 5 3 3 2 2 6 0 1 1 3 8 8 7 1 4 3 8 0 6 7 7 7 1 4 9 2 3 9 2 9 8 6 1

output:

triple correlation 3(2)2(4)1 found

result:

ok single line: 'triple correlation 3(2)2(4)1 found'

Test #15:

score: 0
Accepted
time: 0ms
memory: 116156kb

input:

41
5 2 6 7 9 4 8 1
5 3 3 2 2 6 0 1 1 3 8 8 7 1 4 3
8 2 6
7 7 7 1 4 9 2 3 9 2 9 8 6 1

output:

random sequence

result:

ok single line: 'random sequence'

Test #16:

score: 0
Accepted
time: 0ms
memory: 107888kb

input:

40
9 3 6 9 4 3 1 9 4 6 6 1 3 2 2 8 8 9 0 0 1 6 9 7 7 1 1 5 5 4 3 9 6 4 6 0 0 9 4 1

output:

triple correlation 9(2)6(3)3 found

result:

ok single line: 'triple correlation 9(2)6(3)3 found'

Test #17:

score: 0
Accepted
time: 0ms
memory: 95236kb

input:

40
6 6 4 1 1 9 9 8 8 9 7 9 4 7 6 2 2 6 9
7 5 5 0 0 9 4 7 4 9 9 6 7 9 7 6 7 4 4 3 3

output:

triple correlation 6(3)1(2)9 found

result:

ok single line: 'triple correlation 6(3)1(2)9 found'

Test #18:

score: 0
Accepted
time: 0ms
memory: 104508kb

input:

30
0 0 0 7 8 0 7 6 6 7 8 7 9 9 3 3 5 4 4 2 1 5 7 8 2 1 6 8 6 0

output:

triple correlation 0(1)0(6)6 found

result:

ok single line: 'triple correlation 0(1)0(6)6 found'

Test #19:

score: 0
Accepted
time: 0ms
memory: 95092kb

input:

30
2 3 2 1 2 0 3 1 6 6 0 1 8 8 9
9 7 7 2 4 4 2 1 3 2 1 3 5 5 3

output:

triple correlation 6(4)8(2)9 found

result:

ok single line: 'triple correlation 6(4)8(2)9 found'

Test #20:

score: 0
Accepted
time: 38ms
memory: 166560kb

input:

250
8 2 3 3 4 8 3 2 2 4 3 4 3 8 4 3 2 3 3 9 9 2 8 8 3 3 2 2 8 2 9 8 9 8 3 9 3 3 9 2
3 8 3 4 8 4 8 3 8 8 6 6 6 6 6 4 8 9 2 6
6 6 2 9 8 9 4 9 4 9 3 4 8 4 2 3 8 9 3 3 3 8 2 8 9 2 0 4 4
3 2 3 3 0 5 5 5 5 5 1 0 0 0 5 5 5
1 0 0 0 8 2 0 1 1 3 0 0 0 8 1 1 9 0 0 1 4 8 0 2 9 1 2 4 0 2 8 4 3 8 3 9 4 3 3 4 4 9 ...

output:

triple correlation 6(44)5(54)7 found

result:

ok single line: 'triple correlation 6(44)5(54)7 found'

Test #21:

score: 0
Accepted
time: 249ms
memory: 263772kb

input:

500
8 4 1 6 6 8 2 1 1 1 8 8 6 0 6 6 8 2 2 1
4 2 8 4 6 0 4 4 1 0 1 4 1 6 4 0 8 2 2 2
6 4 4 6 8 4 4 6 1 1 1 0 8 6 6 0 2 1 2 4
0 2 6 8 4 8 8 1 2 8 6 4 0 8 0 2 4 4 4 3
3 3 3 3 3 1 6 3 2 3 0 3 6 8 0 2 3 2 1 3
0 6 1 8 3 3 3 0 0 6 6 4 6 1 4 1 4 0 6 4
4 0 0 4 0 1 0 0 8 8 3 3 3 3 3 3 1 8 3 0
3 6 3 0 8 4 0 3 ...

output:

triple correlation 3(51)3(35)9 found

result:

ok single line: 'triple correlation 3(51)3(35)9 found'

Test #22:

score: 0
Accepted
time: 1341ms
memory: 460948kb

input:

750
5 3 4 3 6 0 1 7 9 4 5 7 0 3 6 4 4 6 2 4 1 4 7 9 7 2 6 8 9 8 5 6 7
5 1 7 9 9 7 2 6 2 8 6
3 2 8 5 5 8 8 9 3 5 3 5 9 4 1 2 8 4 1 0 1 4 2 1 9 8 2 1 1 6 9 5 6 4 3 7 4 4 0 8 7 6 1 1 5 2 5 9 6 2 6 0 8 3 0
7 7 8 6 9 9 1 0 4 2 3 7 7 2 7 7 9 6 7 9 4 9 4 3 2 0 3 2 5 5 7 0 5 7 9 1 2 0 4 9
9 5 2 6 3 0 5 4 2 ...

output:

random sequence

result:

ok single line: 'random sequence'

Test #23:

score: 0
Accepted
time: 2186ms
memory: 458220kb

input:

1000
6 8 1 2 0 4 4 4 0 4 1 4 3 6 3 0 1 1 1 8 4 2 4 3 8 6 0 8 6 8 1 2 1 6 1 6 6 6 8 0
1 1 3 3 1 8 3 2 2 8 8 2 1 3 3 0 3 3 2 3 2 4 0 4 0 3 6 3 1 1 2 0 4 6 0 0 1 2 0 0
2 0 3 1 6 4 2 6 2 0 4 2 6 1 6 0 8 8 4 0 6 3 2 8 4 1 3 1 2 8 1 4 2 6 1 8 0 6 0 4
4 0 1 8 4 1 0 2 3 8 2 8 0 8 1 3 0 4 4 3 0 1 3 3 6 3 4 8...

output:

triple correlation 5(47)7(96)9 found

result:

ok single line: 'triple correlation 5(47)7(96)9 found'

Test #24:

score: 0
Accepted
time: 2336ms
memory: 475760kb

input:

1000
2 6 0 0 8 0 1 9 8 9 8 8 9 0 2 0 0 9 9 8 9 6 0 2 2 6 6 6 9 2 0 7 8 1 9 7 7 0 7 0
7 8 9 1 2 8 6 2 8 8 0 0 6 0 6 7 7 1 2 6 0 2 6 0 0 6 2 7 8 2 0 6 1 6 8 6 0 0 6 1
8 0 2 8 2 0 0 7 9 9 7 1 9 2 8 1 7 9 8 1 9 8 0 6 0 9 0 2 1 1 9 6 9 0 0 1 8 0 7 0
9 0 6 1 8 8 6 6 1 2 9 7 6 8 7 7 6 7 2 8 0 6 0 6 9 2 7 9...

output:

triple correlation 4(65)3(97)5 found

result:

ok single line: 'triple correlation 4(65)3(97)5 found'

Test #25:

score: 0
Accepted
time: 2868ms
memory: 582568kb

input:

1000
3
4
8
4
0
3
3
1
8
6
4
4
9
0
0
6
4
9
3
1
3
0
8
0
2
9
3
3
3
2
0
6
9
3
7
5
8
9
3
7
9
4
4
2
1
7
3
1
6
5
0
9
6
3
5
5
1
5
2
2
3
5
3
1
4
8
5
8
2
7
5
7
1
0
6
0
2
5
5
3
0
0
6
8
1
1
4
6
5
2
2
0
8
4
9
6
1
8
3
2
1
0
1
3
2
2
3
7
1
1
2
5
2
5
7
1
1
9
5
9
8
6
5
1
1
1
2
2
6
3
5
5
3
7
8
5
8
2
8
4
9
1
3
3
5
6
5
9...

output:

random sequence

result:

ok single line: 'random sequence'

Test #26:

score: 0
Accepted
time: 2865ms
memory: 582764kb

input:

1000
7 5 1 4 7 9 4 7 7 2 4 6 6 4 7 8 0 1 4 4 6 4 9 8 0 2 3 4 6 9 6 0 2 9 8 1 0 8 4 6
9 1 6 6 6 6 8 9 8 6 5 4 5 8 6 7 5 6 1 4 7 7 4 2 4 5 5 6 8 0 2 2 2 2 0 6 5 1 7 0
8 2 1 7 4 8 4 3 2 2 4 1 6 1 7 2 4 8 0 5 7 4 6 7 0 9 1 3 2 4 9 8 8 3 5 4 6 8 9 2
5 3 8 2 8 3 4 2 6 5 2 0 4 6 6 3 0 8 4 6 1 2 0 4 2 4 8 3...

output:

random sequence

result:

ok single line: 'random sequence'

Test #27:

score: 0
Accepted
time: 3003ms
memory: 585304kb

input:

1000
5 7 1 5 9 1 7 0 6 9 2 1 6 6 7 3 9 6 6 4 1 5 7 9 0 3 1 8 2 7 2 8 2 8 4 8 8 5 4 2
9 2 2 0 6 6 1 9 2 8 6 8 5 1 5 6 2 1 8 1 5 8 0 1 1 3 7 9 5 7 1 4 0 2 9 9 2 3 4 8
6 5 2 9 3 7 2 7 8 1 9 7 5 6 1 2 8 7 6 6 6 5 3 4 5 4 7 1 2 3 2 0 8 3 0 3 6 4 5 6
4 8 8 2 4 7 3 9 3 7 3 7 0 7 7 6 3 5 2 4 2 0 6 3 6 3 8 5...

output:

random sequence

result:

ok single line: 'random sequence'

Test #28:

score: 0
Accepted
time: 0ms
memory: 116744kb

input:

41
1 9 4 2 5 6 3 7 8 0 7 1 6 5 2 4 2 3 8 5 6 0 9 8 4 1 5 8 2 6 7 3 0 9 0 1 6 5 2 4 8

output:

triple correlation 1(3)2(3)3 found

result:

ok single line: 'triple correlation 1(3)2(3)3 found'

Test #29:

score: 0
Accepted
time: 0ms
memory: 116904kb

input:

41
1 9 4 2 5 6 3 7 8 0 7 1 6 5 2 4 2 3 5 6 0 9 8 4 1 5 8 2 6 7 3 0 9 0 1 6 5 2 4 8 3

output:

triple correlation 1(3)2(3)3 found

result:

ok single line: 'triple correlation 1(3)2(3)3 found'

Test #30:

score: 0
Accepted
time: 3ms
memory: 114196kb

input:

41
1 9 4 2 5 6 3 7 8 9 7 1 6 5 2 4 2 3 5 6 0 9 8 4 1 5 8 2 6 7 3 0 9 0 1 6 5 2 4 8 4

output:

random sequence

result:

ok single line: 'random sequence'

Test #31:

score: 0
Accepted
time: 4ms
memory: 114056kb

input:

41
9 8 7 6 2 0 4 5 6 7 3 1 8 9 0 4 2 7 6 5 4 0 3 0 4 1 1 6 0 9 2 2 9 0 4 9 3 3 6 6 5

output:

triple correlation 1(5)2(6)3 found

result:

ok single line: 'triple correlation 1(5)2(6)3 found'

Test #32:

score: 0
Accepted
time: 4ms
memory: 111864kb

input:

41
1 9 8 7 6 2 0 4 5 6 7 3 1 8 9 0 4 2 7 6 5 4 0 3 0 4 1 1 6 0 9 2 2 9 0 4 9 3 3 6 6

output:

triple correlation 1(5)2(6)3 found

result:

ok single line: 'triple correlation 1(5)2(6)3 found'

Test #33:

score: 0
Accepted
time: 4ms
memory: 111668kb

input:

41
2 9 8 7 6 2 0 4 5 6 7 3 1 8 9 0 4 2 7 6 5 4 0 3 0 4 1 1 6 0 9 2 2 9 0 4 9 3 3 6 6

output:

random sequence

result:

ok single line: 'random sequence'

Test #34:

score: 0
Accepted
time: 4ms
memory: 120500kb

input:

50
1 2 3 4 5 5 7 8 9 2 0 3 6 8 3 0 6 9 4 0 8 0 5 1 0 3 5 8 9 0 0 2 4 6 3 0 3 7 9 4 3 0 9 1 4 7 2 5 8 3

output:

triple correlation 0(5)0(6)0 found

result:

ok single line: 'triple correlation 0(5)0(6)0 found'