QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#737792#8040. Let Them Eat Cakeryh7#WA 41ms14416kbC++171.5kb2024-11-12 16:52:422024-11-12 16:52:43

Judging History

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

  • [2024-11-12 16:52:43]
  • 评测
  • 测评结果:WA
  • 用时:41ms
  • 内存:14416kb
  • [2024-11-12 16:52:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using VI = vector<int>;
using PII = pair<int,int>;
using VVI = vector<vector<int>>;
const ll mod = 998244353;
const ll INF = 1e18;
const int N = 2e5 + 10;
void solve(){
	
}
int n;
int a[N];
int nex[N];
int pre[N];
int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   //int T;cin>>T;while(T--)solve();
    cin>>n;
    for(int i = 1 ; i <= n ; i++) cin>>a[i];
    
    for(int i = 1 ; i <= n ; i++){
    	nex[i] = i + 1;
    	pre[i] = i - 1;
    }
    
    set<int> s;
    for(int i = 1 ; i <= n ; i++){
    	if(a[i] < a[i + 1] || a[i] < a[i - 1]){
    		s.insert(i);
    	}
    }
   /* for(auto x : s){
    	cout<<x<<" ";
    }*/
    int ct = 0;
    VI vis(n + 1 , 0);
    for(int i = 1 ; i <= n ; i++){
    	set<int> tmp;
    	for(auto x : s){
    		vis[x] = 1;
    		nex[pre[x]] = nex[x];
    		pre[nex[x]]	= pre[x];
    		if(pre[x] != 0) tmp.insert(pre[x]);
    		if(nex[x] != n + 1) tmp.insert(nex[x]);
    		//if(a[pre[x]] < a[nex[x]]) tmp.insert(pre[x]);
    		//else tmp.insert(nex[x]);
    	}
    	
    	//for(auto x : tmp) cout<<x<<" ";
		s.clear();
		    	
    	for(auto x : tmp){
    		if(vis[x]) continue;
    		if(a[x] > a[pre[x]] && a[x] > a[nex[x]]) continue;
    		s.insert(x);
    	}
    	
    	if(s.size() == 0){
    		 ct = i ;
    		 break;
    	}
    	
    	
 
    	
    }
    
    
    
    cout<<ct<<"\n";
    
    
    
    
}


//5 4 3 2 1
//5 4 3 2 1

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3572kb

input:

5
1 2 3 4 5

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

5
1 5 3 4 2

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

2
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 36ms
memory: 14416kb

input:

100000
100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 9995...

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 40ms
memory: 11044kb

input:

100000
28708 58898 66379 81466 37843 38494 7200 13212 70705 98441 68380 79776 45228 18860 96220 19831 27343 59978 23624 87081 30257 26315 23862 7186 37684 193 70599 29284 14627 30319 51080 95350 17977 32253 58304 19841 67584 44345 69298 63002 48446 5959 8500 12298 59988 55130 56346 5380 23327 13969 ...

output:

11

result:

ok 1 number(s): "11"

Test #6:

score: 0
Accepted
time: 40ms
memory: 12384kb

input:

100000
72743 44886 88887 79534 73039 59668 25271 79700 79511 367 86467 30576 66004 39449 41715 4566 91620 76947 63324 90583 85057 86478 73270 85020 28824 27787 24887 1886 22406 74871 46760 36653 48917 12845 39253 48945 16711 32355 1799 30249 83263 24750 74089 94226 11670 71457 55091 2952 20006 73975...

output:

11

result:

ok 1 number(s): "11"

Test #7:

score: 0
Accepted
time: 41ms
memory: 10992kb

input:

100000
31628 44 67381 28236 32853 24077 80612 86645 35088 57122 15372 21707 3966 38717 87884 74738 52799 36501 64678 6205 33171 13185 50485 15888 91467 32344 9196 51541 2603 95686 13916 83347 94908 52434 71235 59263 30478 23262 79576 93981 77940 27266 36940 2663 36398 85275 86173 39906 99669 37727 2...

output:

10

result:

ok 1 number(s): "10"

Test #8:

score: 0
Accepted
time: 19ms
memory: 7412kb

input:

65535
32768 16384 49152 8192 40960 24576 57344 4096 36864 20480 53248 12288 45056 28672 61440 2048 34816 18432 51200 10240 43008 26624 59392 6144 38912 22528 55296 14336 47104 30720 63488 1024 33792 17408 50176 9216 41984 25600 58368 5120 37888 21504 54272 13312 46080 29696 62464 3072 35840 19456 52...

output:

16

result:

ok 1 number(s): "16"

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 5908kb

input:

1
1

output:

1

result:

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