QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#631828 | #515. A Random Problem | chuchu# | AC ✓ | 2751ms | 951064kb | C++14 | 2.5kb | 2024-10-12 10:29:26 | 2024-10-12 10:29:28 |
Judging History
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'