QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#46570#1096. Best Solution UnknownmouseyWA 2ms3600kbC++2.1kb2022-08-30 14:08:192022-08-30 14:08:22

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 14:08:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3600kb
  • [2022-08-30 14:08:19]
  • 提交

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+bonus>=best)
	{
	    if(bonus==0) v.pb(max.s);
	}
	if(max.f!=best)
	{
	    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);
	}
}

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: 0
Wrong Answer
time: 2ms
memory: 3600kb

input:

3
3 2 2

output:

2
1 3 

result:

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