oj.uz

Submission #918843

# Submission time Handle Problem Language Result Execution time Memory
918843 2024-01-30T14:12:36 Z gs25 Flip it and Stick it (CCO23_day2problem1) C++17
18 / 25
 3 ms 1248 KB 
#include <bits/stdc++.h> 

using namespace std; 


void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V> void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T> void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V> void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define dbg(x...)                                                              \
  cerr << " [" << #x << "] = [";    \
  _print(x);                                                                   \

#else
#define dbg(x...)
#endif	

#define int long long
#define rrep(i,n) for(int i=1; i<=n; i++)
#define rep(i,n) for(int i=0; i<n; i++)
#define all(v) (v).begin(), (v).end() 
#define ff first 
#define ss second 
#define pb push_back


void solve(){
	string s,t; cin >> s >> t; 
	if(t.size()==1){
		int ch = t[0]; 
		bool flag = true; 
		for(auto si : s) if(si==ch) flag=false; 
		cout << (flag ? "0" : "-1"); 
		return; 
	}
	if(t.size()==2){
		if(t[0]!=t[1]){
			int n = s.size();
			int tmp = 0;  
			for(int i=0;i<n-1;i++){
				if(s[i]==t[0]&&s[i+1]==t[1]) tmp++; 
			}
			cout << tmp; return; 
		}
		if(t[0]==t[1]){
			int n = s.size(); 
			int c1=0,c2=0,cc=0; 
			for(int i=0; i<n; i++){
				if(s[i]==t[0])c1++; 
				else c2++;
				if(i>0 && s[i]==t[0] && s[i-1]==t[0]) cc++; 
			}
			if(c2+1<c1) cout << "-1"; 
			else{
				cout << cc; 
			}
			return ;
		}
	}
	if(t.size()==3){
		if(t[0]!=t[2]){
			if(t[0]!=t[1]){
				reverse(all(s)); reverse(all(t)); 
			}	
			int tmp = 0; 
			int n = s.size(); 
			for(int i=0;i<n;){
				if(s[i]==t[0]){
					int j = i; 
					while(j<n && s[j]==t[0]) j++;
					j--;
					if(j==i || j==n-1){
						i=j+1; continue; 
					} 
					tmp++; i=j+1; 
				}
				else i++; 
			}
			cout << tmp;
			return;
		}
		if(t[0]!=t[1]){
			int n = s.size();
			int cnt = 0; 
			for(int i=0;i<n;i++){
				if(i>0&&i<n-1&& s[i-1]==t[0] && s[i]==t[1]&&s[i+1]==t[2]) cnt++;
			}
			cout << (cnt+1)/2; return;
		}
		int n = s.size(); 
		int c1=0,c2=0,cc=0; 
		assert(t[0]==t[1] && t[1]==t[2]); 
		for(int i=0; i<n; i++){
			if(s[i]==t[0])c1++; 
			else c2++;
		}
		if(2*c2+2<c1) cout << "-1"; 
		else{
			int cnt = 0, cnt_single=0, cnt_good=0;
			vector<int> v;  
			for(int i=0; i<n;){
				int j=i;
				while(j<n && s[j]==s[i]) j++; 
				if(s[i]==t[0]){
					if(j==i+1) cnt_single++; 
					else v.pb(j-i); 
				}
				if(s[i]==t[1]){
					cnt_good += (j-i-1); 
				}
				i=j; 
			}
			if(s[0]!=t[0]) cnt_good++; 
			if(s[n-1]!=t[0]) cnt_good++; 
			for(auto d : v){
				while(d>=4 && cnt_good) d-=2,cnt_good--,cnt++; 
				while(d>=3 && cnt_single) d-=1,cnt_single--,cnt++; 
				while(d>=3 && cnt_good) d-=1,cnt_good--,cnt++;   
			}
			cout << cnt; 			
		}
		return; 
	}
	cout << "-1";
}

int32_t main(void){
	ios::sync_with_stdio(false); 
	cout.tie(nullptr); 
	cin.tie(nullptr);
	int t =1; // cin >> t; 
	while(t--) solve(); 
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:123:17: warning: unused variable 'cc' [-Wunused-variable]
  123 |   int c1=0,c2=0,cc=0;
      |                 ^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 856 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 1 ms 856 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 2 ms 1116 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 1 ms 856 KB Output is correct
23 Correct 2 ms 856 KB Output is correct
24 Correct 2 ms 856 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 2 ms 856 KB Output is correct
28 Correct 2 ms 1112 KB Output is correct
29 Correct 1 ms 856 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 2 ms 856 KB Output is correct
32 Correct 2 ms 860 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 1 ms 344 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 1060 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 992 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 856 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 1 ms 856 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 2 ms 856 KB Output is correct
18 Correct 1 ms 856 KB Output is correct
19 Correct 2 ms 856 KB Output is correct
20 Correct 1 ms 1112 KB Output is correct
21 Correct 1 ms 856 KB Output is correct
22 Correct 1 ms 1056 KB Output is correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 1060 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 992 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 0 ms 460 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 856 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Correct 2 ms 856 KB Output is correct
28 Correct 1 ms 856 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 2 ms 856 KB Output is correct
31 Correct 1 ms 856 KB Output is correct
32 Correct 2 ms 856 KB Output is correct
33 Correct 1 ms 1112 KB Output is correct
34 Correct 1 ms 856 KB Output is correct
35 Correct 1 ms 1056 KB Output is correct
36 Correct 0 ms 344 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 1 ms 856 KB Output is correct
39 Incorrect 3 ms 1248 KB Output isn't correct
40 Halted 0 ms 0 KB -