Submission #918843

#	Time	Username	Problem	Language	Result	Execution time	Memory
918843		gs25	Flip it and Stick it (CCO23_day2problem1)	C++17	18 / 25	3 ms	1248 KiB

Main

#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 (stderr)

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 / 1
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 7