QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#631828#515. A Random Problemchuchu#AC ✓2751ms951064kbC++142.5kb2024-10-12 10:29:262024-10-12 10:29:28

Judging History

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

  • [2024-10-12 10:29:28]
  • 评测
  • 测评结果:AC
  • 用时:2751ms
  • 内存:951064kb
  • [2024-10-12 10:29:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int short
typedef vector<int> vi;
#define pb push_back

pair<int, int> cnt[11][11][1001][1001];
int cnt1[11][11][1001][1001];
int cnt2[11][11][1001][1001];

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < 11; i++){
		for(int j = 0; j < 11; j++){
			for(int k = 0; k < 1001; k++){
				for(int l = 0; l < 1001; l++){
					cnt[i][j][k][l].first = -1;
					cnt[i][j][k][l].second = -1;
					cnt1[i][j][k][l] = -1;
					cnt2[i][j][k][l] = -1;
				}
			}
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			for(int k = j + 1; k < n; k++){
				//cnt[a[i]][a[j]][j - i][k - j]
				//0
				if(cnt[a[i]][a[j]][j - i][k - j].first == -1){
					cnt[a[i]][a[j]][j - i][k - j].first = a[k];
					cnt[a[i]][a[j]][j - i][k - j].second = 1;
				}
				else if(cnt[a[i]][a[j]][j - i][k - j].first != -2){
					if(cnt[a[i]][a[j]][j - i][k - j].first != a[k]){
						cnt[a[i]][a[j]][j - i][k - j].first = -2;
					}
					cnt[a[i]][a[j]][j - i][k - j].second++;
				}
				//1
				if(cnt1[a[i]][a[k]][j - i][k - j] == -1){
					cnt1[a[i]][a[k]][j - i][k - j] = a[j];
				}
				else if(cnt1[a[i]][a[k]][j - i][k - j] != -2){
					if(cnt1[a[i]][a[k]][j - i][k - j] != a[j]){
						cnt1[a[i]][a[k]][j - i][k - j] = -2;
					}
				}
				//2
				if(cnt2[a[j]][a[k]][j - i][k - j] == -1){
					cnt2[a[j]][a[k]][j - i][k - j] = a[i];
				}
				else if(cnt2[a[j]][a[k]][j - i][k - j] != -2){
					if(cnt2[a[j]][a[k]][j - i][k - j] != a[i]){
						cnt2[a[j]][a[k]][j - i][k - j] = -2;
					}
				}
			}
		}
	}
	int num = (n + 39) / 40 + 1;
	int ok = 0;
	array<int, 6> ans = {(int)1e4, (int)1e4, (int)1e4, (int)1e4, (int)1e4, (int)1e4};
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			for(int k = j + 1; k < n; k++){
				if(cnt[a[i]][a[j]][j - i][k - j].first >= 0 && cnt[a[i]][a[j]][j - i][k - j].second >= num){
					if(cnt1[a[i]][a[k]][j - i][k - j] >= 0 && cnt2[a[j]][a[k]][j - i][k - j] >= 0){
						ok = 1;
						if(i < ans[5]){
							ans = {a[i], j - i, a[j], k - j, a[k], i};
						}
						if(i == ans[5] && j - i < ans[1]){
							ans = {a[i], j - i, a[j], k - j, a[k], i};
						}
						else if(i == ans[5] && j - i == ans[1] && k - j < ans[3]){
							ans = {a[i], j - i, a[j], k - j, a[k], i};
						}
					}
				}
			}
		}
	}
	if(!ok){
		cout << "random sequence\n";
		return 0;
	}
	cout << "triple correlation " << ans[0] << "(" << ans[1] << ")" << ans[2] << "(" << ans[3] << ")" << ans[4] << " found\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 59ms
memory: 950760kb

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: 72ms
memory: 950760kb

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: 79ms
memory: 950760kb

input:

1
0

output:

random sequence

result:

ok single line: 'random sequence'

Test #4:

score: 0
Accepted
time: 55ms
memory: 951016kb

input:

2
0 1

output:

random sequence

result:

ok single line: 'random sequence'

Test #5:

score: 0
Accepted
time: 87ms
memory: 950812kb

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: 52ms
memory: 950860kb

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: 59ms
memory: 951064kb

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: 67ms
memory: 950700kb

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: 91ms
memory: 950752kb

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: 84ms
memory: 950976kb

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: 63ms
memory: 950860kb

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: 71ms
memory: 951012kb

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: 63ms
memory: 950980kb

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: 95ms
memory: 950832kb

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: 92ms
memory: 950812kb

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: 74ms
memory: 950752kb

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: 88ms
memory: 950756kb

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: 80ms
memory: 950816kb

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: 84ms
memory: 950756kb

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: 95ms
memory: 950756kb

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: 429ms
memory: 951052kb

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: 1303ms
memory: 950760kb

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: 2322ms
memory: 951048kb

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: 2550ms
memory: 951012kb

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: 2751ms
memory: 950980kb

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: 2599ms
memory: 950816kb

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: 2685ms
memory: 950760kb

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: 79ms
memory: 951020kb

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: 68ms
memory: 951048kb

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: 83ms
memory: 950700kb

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: 63ms
memory: 951060kb

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: 72ms
memory: 950980kb

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: 79ms
memory: 950992kb

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: 64ms
memory: 950752kb

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'