QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#631797 | #515. A Random Problem | chuchu# | WA | 83ms | 951012kb | C++14 | 2.4kb | 2024-10-12 10:19:49 | 2024-10-12 10:19:50 |
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[j]){
cnt2[a[j]][a[k]][j - i][k - j] = -2;
}
}
}
}
}
int num = (n + 39) / 40 + 1;
int ok = 0;
array<int, 5> ans = {(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(j - i < ans[1]){
ans = {a[i], j - i, a[j], k - j, a[k]};
}
else if(j - i == ans[1] && k - j < ans[3]){
ans = {a[i], j - i, a[j], k - j, a[k]};
}
}
}
}
}
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 60ms
memory: 950860kb
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: 40ms
memory: 950756kb
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: 80ms
memory: 950700kb
input:
1 0
output:
random sequence
result:
ok single line: 'random sequence'
Test #4:
score: 0
Accepted
time: 83ms
memory: 950816kb
input:
2 0 1
output:
random sequence
result:
ok single line: 'random sequence'
Test #5:
score: -100
Wrong Answer
time: 55ms
memory: 951012kb
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 1(3)1(3)0 found
result:
wrong answer 1st lines differ - expected: 'triple correlation 8(3)2(15)5 found', found: 'triple correlation 1(3)1(3)0 found'