oj.uz

Submission #40946

# Submission time Handle Problem Language Result Execution time Memory
40946 2018-02-09T23:39:27 Z wzy Difference (POI11_roz) C++14
100 / 100
 833 ms 16684 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pii pair<int,int>
#define ieps (int) 1e6
#define eps (int) 1e9
#define mp make_pair
#define pb push_back
vector<int> hist[27];
int n;
string s;
int ansj = 0;


void solve(int pos , int neg){
	int cnta = 0 , cntb = 0 , curr = 0 , leftp = 0 , foineg = false;
	for(int i = 0 ; i < hist[pos].size() + hist[neg].size() ; i++){
		if(cnta == hist[pos].size()){
			if(!foineg){
				ansj = max(ansj , curr - 1);
			}
			return;
		}
		else if(cntb == hist[neg].size()){
			if(!foineg){
				break;
			}
			while(cnta++ <hist[pos].size()){
				curr++;
			}
			if(foineg)ansj = max(ansj , curr);
			break;
		}
		else{
			if(hist[pos][cnta] < hist[neg][cntb]){
				curr++;
				cnta++;
				if(foineg) ansj = max(ansj , curr);
			}
			else{
				cntb++;
				if(curr - 1 >=0){
					curr--;
					foineg = true;
					if(foineg) ansj = max(ansj , curr);
				}
				else{
					foineg = false;
					curr = 0;
				}
			}
		}
	}
	return;
}



int32_t main(){
	scanf("%d" , &n);
	s.resize(n);
	scanf("%s" , &s[0]);
	for(int i = 0 ; i < n;i++){
		hist[s[i] - 'a'].pb(i);
	}
	for(char i = 'a' ; i <= 'z' ; i++){
		for(char j = 'a' ; j <= 'z'; j++){
			if(i == j) continue;
			solve(i-'a' , j-'a');
		}
	}
	for(int i = 0 ; i < n;i++){
		hist[s[i] - 'a'].clear();
	}
	reverse(s.begin() , s.end());
	for(int i = 0 ; i < n;i++){
		hist[s[i] - 'a'].pb(i);
	}
	for(char i = 'a' ; i <= 'z' ; i++){
		for(char j = 'a' ; j <= 'z'; j++){
			if(i == j) continue;
			solve(i-'a' , j-'a');
		}
	}
	printf("%d\n" , ansj);
}

Compilation message

roz.cpp: In function 'void solve(int, int)':
roz.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < hist[pos].size() + hist[neg].size() ; i++){
                    ^
roz.cpp:19:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(cnta == hist[pos].size()){
           ^
roz.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if(cntb == hist[neg].size()){
                ^
roz.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(cnta++ <hist[pos].size()){
                 ^
roz.cpp:17:39: warning: unused variable 'leftp' [-Wunused-variable]
  int cnta = 0 , cntb = 0 , curr = 0 , leftp = 0 , foineg = false;
                                       ^
roz.cpp: In function 'int32_t main()':
roz.cpp:61:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &n);
                  ^
roz.cpp:63:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s" , &s[0]);
                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 1 ms 464 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 616 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 2 ms 644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 684 KB Output is correct
2 Correct 2 ms 684 KB Output is correct
3 Correct 2 ms 724 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 740 KB Output is correct
2 Correct 2 ms 740 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 748 KB Output is correct
2 Correct 2 ms 748 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1404 KB Output is correct
2 Correct 2 ms 1404 KB Output is correct
3 Correct 5 ms 1404 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 7884 KB Output is correct
2 Correct 2 ms 7884 KB Output is correct
3 Correct 381 ms 7884 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 9500 KB Output is correct
2 Correct 555 ms 9572 KB Output is correct
3 Correct 128 ms 10020 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 12348 KB Output is correct
2 Correct 80 ms 12572 KB Output is correct
3 Correct 44 ms 13472 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 748 ms 14800 KB Output is correct
2 Correct 52 ms 15176 KB Output is correct
3 Correct 140 ms 16684 KB Output is correct