QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719576 | #515. A Random Problem | kevinyang# | AC ✓ | 3003ms | 585304kb | C++20 | 2.9kb | 2024-11-07 04:01:40 | 2024-11-07 04:01:41 |
Judging History
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'