QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#46564 | #1096. Best Solution Unknown | mousey | WA | 558ms | 424912kb | C++ | 2.3kb | 2022-08-30 13:54:55 | 2022-08-30 13:54:57 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define db double
#define ldb long double
#define pdb pair <double, double>
#define YES cout<<"YES"
#define NO cout<<"NO"
#define endl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll>
#define mp make_pair
#define pb push_back
#define f first
#define s second
using namespace std;
const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const ll N=1e6;
ll n, a[N+5];
vll v;
pll st[20][N+5];
ll grt;
void input()
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
}
}
void precalc()
{
for(int i = 1; i <= n; i++)
{
st[0][i]={a[i], i};
}
for(int i = 1; i < 20; i++)
{
for(int j = 1; j+(1<<i)-1 <= n; j++)
{
st[i][j]=max(st[i-1][j], st[i-1][j+(1ll<<(i-1))]);
}
}
}
pll find_max(ll l, ll r)
{
ll loga=(ll) log2(r-l+1);
return max(st[loga][l], st[loga][r-(1ll<<loga)+1]);
}
void dnc(ll l, ll r, ll best, ll bonus)
{
if(l>r) return;
pll max=find_max(l, r);
// cout << l << " " << r << " " << best << " " << bonus << " " << max.f << " " << grt << "\n";
if(max.f+r-l>=best)
{
if(bonus==0) v.pb(max.s);
else if(max.f+bonus>=grt) v.pb(max.s);
}
if(max.f!=grt)
{
if(best==grt)
{
dnc(l, max.s-1, max.f, r-l);
dnc(max.s+1, r, max.f, r-l);
}
else
{
dnc(l, max.s-1, max.f, bonus);
dnc(max.s+1, r, max.f, bonus);
}
}
else
{
dnc(l, max.s-1, max.f, 0);
dnc(max.s+1, r, max.f, 0);
}
}
void solve()
{
grt=find_max(1, n).f;
dnc(1, n, grt, 0);
sort(v.begin(), v.end());
cout << v.size() << "\n";
for(auto i: v) cout << i << " ";
}
int main()
{
// auto start_time = chrono::high_resolution_clock::now();
// freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int t=1;
while(t--)
{
input();
precalc();
solve();
endl;
}
// auto end_time = chrono::high_resolution_clock::now();
// double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
// cout << "\n[ " << duration << " ms ]\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3836kb
input:
3 3 2 2
output:
3 1 2 3
result:
ok 4 number(s): "3 1 2 3"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
3 1 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
5 1 2 3 5 5
output:
3 3 4 5
result:
ok 4 number(s): "3 3 4 5"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
1 10
output:
1 1
result:
ok 2 number(s): "1 1"
Test #5:
score: 0
Accepted
time: 558ms
memory: 424904kb
input:
1000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 100000...
output:
1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
result:
ok 1000001 numbers
Test #6:
score: 0
Accepted
time: 351ms
memory: 424640kb
input:
1000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
result:
ok 1000001 numbers
Test #7:
score: 0
Accepted
time: 491ms
memory: 424912kb
input:
1000000 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 960762215 96...
output:
1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
result:
ok 1000001 numbers
Test #8:
score: 0
Accepted
time: 533ms
memory: 424856kb
input:
1000000 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 824165353 82...
output:
1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
result:
ok 1000001 numbers
Test #9:
score: -100
Wrong Answer
time: 3ms
memory: 3980kb
input:
1000 10 9 8 3 8 8 2 5 9 6 4 4 5 1 2 4 9 5 8 6 6 3 8 7 4 6 7 3 6 5 10 8 8 7 2 5 8 7 4 1 1 5 5 4 9 8 6 2 7 7 3 5 4 1 7 7 6 5 6 8 4 4 4 2 9 3 3 1 8 1 7 3 10 4 3 1 2 7 4 6 3 7 6 2 1 1 1 10 6 6 3 9 2 6 10 3 7 7 1 5 10 10 6 4 9 6 7 1 10 2 10 10 10 5 2 6 4 9 4 7 3 5 10 9 5 10 4 6 7 5 3 5 7 10 4 6 9 5 10 5 ...
output:
573 1 2 3 5 6 9 10 11 12 13 16 17 19 20 21 23 24 26 27 29 31 32 33 34 37 38 39 40 42 43 45 46 47 49 50 52 53 55 56 57 59 60 61 62 65 66 69 71 73 74 75 77 78 80 82 83 85 86 87 88 89 92 95 97 98 101 102 105 107 109 111 112 113 114 116 118 120 123 124 126 128 129 130 132 133 134 137 139 141 142 144 147...
result:
wrong answer 1st numbers differ - expected: '517', found: '573'