# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
29732 |
2017-07-20T11:49:24 Z |
cdemirer |
Secret (JOI14_secret) |
C++14 |
|
629 ms |
9920 KB |
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
int _N;
int _A[1000];
int hesaplar[1000][1000];
void calc(int l, int r) {
if (l == r) {
return;
}
int mid = (l+r)/2;
if (r - l == 1) {
hesaplar[mid][mid+1] = Secret(_A[mid], _A[mid+1]);
hesaplar[mid+1][mid] = _A[mid];
return;
}
calc(l, mid);
calc(mid+1, r);
int lmid = (l+mid)/2, rmid = (mid+1+r)/2;
if (mid-1 > lmid) hesaplar[mid][mid-1] = _A[mid-1];
for (int i = mid-2; i > lmid; i--) {
hesaplar[mid][i] = Secret(_A[i], hesaplar[mid][i+1]);
}
if (lmid == mid-1) {
hesaplar[mid][lmid] = _A[lmid];
}
else {
hesaplar[mid][lmid] = Secret(_A[lmid], hesaplar[mid][lmid+1]);
}
for (int i = lmid-1; i >= l; i--) {
//cerr << "A" << endl;
//cerr << "lmid, i, mid, lmid+1 : " << lmid << " " << i << " " << mid << " " << mid+1 << endl;
hesaplar[mid][i] = Secret(hesaplar[lmid][i], hesaplar[mid][lmid]);
//cerr << "B" << endl;
}
for (int i = mid+1; i < rmid; i++) {
hesaplar[mid][i] = Secret(hesaplar[mid][i-1], _A[i]);
}
for (int i = rmid; i <= r; i++) {
hesaplar[mid][i] = Secret(hesaplar[mid][rmid-1], hesaplar[rmid][i]);
}
}
void Init(int N, int A[]) {
memset(hesaplar, -1, sizeof(hesaplar));
_N = N;
for (int i = 0; i < N; i++) _A[i] = A[i];
for (int i = 0; i < N; i++) hesaplar[i][i] = _A[i];
calc(0, _N-1);
}
int Query(int L, int R) {
int l = 0, r = _N-1;
while (true) {
//cerr << l << " " << r << " : " << L << " " << R << endl;
int mid = (l+r)/2;
if (L == R && L == mid) return _A[mid];
else if (L <= mid && R >= mid) {
int a = hesaplar[mid][L];
int b = hesaplar[mid][R];
return Secret(a, b);
}
else if (R == mid) {
return Secret(hesaplar[mid][L], _A[mid]);
}
else if (R == mid-1) {
return hesaplar[mid][L];
}
else if (L == mid) {
return hesaplar[mid][R];
}
else if (R < mid) {
r = mid;
}
else if (L > mid) {
l = mid+1;
}
else {
cerr << "Impossible branch" << endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
163 ms |
9920 KB |
Wrong Answer: Query(255, 409) - expected : 307522235, actual : 38999632. |
2 |
Incorrect |
163 ms |
9920 KB |
Wrong Answer: Query(127, 153) - expected : 342921603, actual : 542288066. |
3 |
Incorrect |
159 ms |
9920 KB |
Wrong Answer: Query(128, 153) - expected : 959658850, actual : 219466354. |
4 |
Incorrect |
603 ms |
9920 KB |
Wrong Answer: Query(374, 396) - expected : 402362963, actual : 342036658. |
5 |
Incorrect |
599 ms |
9920 KB |
Wrong Answer: Query(703, 706) - expected : 857111674, actual : 525219936. |
6 |
Incorrect |
596 ms |
9920 KB |
Wrong Answer: Query(117, 121) - expected : 983571657, actual : 722631920. |
7 |
Incorrect |
629 ms |
9920 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |
8 |
Incorrect |
609 ms |
9920 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |
9 |
Incorrect |
623 ms |
9920 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |
10 |
Incorrect |
603 ms |
9920 KB |
Output isn't correct - number of calls to Secret by Init = 8466, maximum number of calls to Secret by Query = 1 |