QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#46599#1096. Best Solution UnknownmouseyWA 2ms3772kbC++2.0kb2022-08-30 15:06:392022-08-30 15:06:40

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 15:06:40]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3772kb
  • [2022-08-30 15:06:39]
  • 提交

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];

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)
{
    if(l>r) return;
	pll maxi=find_max(l, r);
//	cout << l << " " << r << " " << best << " " << maxi.f << "\n";
	if(maxi.f+r-l>=best) v.pb(maxi.s);
	dnc(l, maxi.s-1, max(best, maxi.f-(r-maxi.s)));
	dnc(maxi.s+1, r, max(best, maxi.f-(r-maxi.s)));
}

void solve()
{
    dnc(1, n, 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: 3772kb

input:

3
3 2 2

output:

3
1 2 3 

result:

ok 4 number(s): "3 1 2 3"

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3728kb

input:

3
1 2 1

output:

3
1 2 3 

result:

wrong answer 1st numbers differ - expected: '1', found: '3'