QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#46564#1096. Best Solution UnknownmouseyWA 558ms424912kbC++2.3kb2022-08-30 13:54:552022-08-30 13:54:57

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-30 13:54:57]
  • 评测
  • 测评结果:WA
  • 用时:558ms
  • 内存:424912kb
  • [2022-08-30 13:54:55]
  • 提交

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'