oj.uz

Submission #1082720

# Submission time Handle Problem Language Result Execution time Memory
1082720 2024-09-01T09:49:39 Z tte0 Flip it and Stick it (CCO23_day2problem1) C++17
13 / 25
 9 ms 9556 KB 
/*
Author: Teoman Ata Korkmaz
*/
#pragma GCC optimize("O3,fast-math,unroll-loops,no-stack-protector")
#include <bits/stdc++.h> 
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define int ll
#define ff first
#define ss second
#define endl '\n'
#define spc ' '
#define pb push_back
#define e2(x) (1LL<<(x))
#define lg(x) (__lg(x))
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) ((x/gcd(x,y))*y)
#define smrt(i) (double(sqrt(8*(i)+1)-1)/2)
#define ssum(x) ((x)*((x)+1)/2)
#define isint(x) (ceil((x))==floor((x)))
#define no cout<<"NO"<<endl
#define yes cout<<"YES"<<endl
#define cendl cout<<endl
#define mset(x,y) memset(x,y,sizeof(x))
#define popcnt(x) __builtin_popcountll(x)
#define clz(x) __builtin_clz(x)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define clock() uint64_t(chrono::high_resolution_clock::now().time_since_epoch().count())
#define compress(x) sort(all(x));x.resize(unique(all(x))-x.begin())
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cerr.tie(NULL);cout<<fixed<<setprecision(0);cerr<<fixed<<setprecision(0)
#define fileio freopen("out.txt","w",stdout);freopen("in.txt","r",stdin)
#define usacoio(s) freopen((s + str(".in")).c_str(), "r", stdin);freopen((s + str(".out")).c_str(), "w", stdout)
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
using namespace std;
//using namespace __gnu_pbds;
typedef int_fast32_t i32;
typedef int_fast64_t ll;
typedef long double ldouble;
typedef string str;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair<ii,ii> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pair<char,int>> vci;
typedef vector<str> vstr;
typedef map<int,int> mii;
typedef map<char,int> mci;
typedef map<str,int> msi;
typedef map<int,vi> miv;
typedef unordered_map<int,int> umii;
typedef unordered_map<char,int> umci;
typedef unordered_map<str,int> umsi;
typedef unordered_map<int,vi> umiv;
typedef set<int> sti;
typedef set<char> stc;
typedef set<str> sts;
typedef multiset<int> msti;
typedef multiset<char> mstc;
typedef multiset<str> msts;
inline int segsum(int start,int end,int step){
    if(end<start)return 0;
    return (((end-start)/step+1)*(start+end))>>1;
}
inline int fp(int b,int p,int mod=1e9+7){
    int ans=1;
    while(p){
        if(p&1)ans=(ans*b)%mod;
        p>>=1;
        b=(b*b)%mod;
    }
    return ans;
}
template<typename InputIterator,typename T = int>
T accumulate(InputIterator first,InputIterator last,T init = T{}) {
    for (; first != last; ++first) {
        init += *first;
    }
    return init;
}
template<typename T,typename T2>inline pair<T,T2> operator+(const pair<T,T2>&a,const pair<T,T2>& b){return {a.ff+b.ff,a.ss+b.ss};}
template<typename T,typename T2>inline pair<T,T2> operator-(const pair<T,T2>&a,const pair<T,T2>& b){return {a.ff-b.ff,a.ss-b.ss};}
template<typename T,typename T2>inline pair<T,T2> operator*(const pair<T,T2>&a,const pair<T,T2>& b){return {a.ff*b.ff,a.ss*b.ss};}
template<typename T,typename T2>inline pair<T,T2> operator/(const pair<T,T2>&a,const pair<T,T2>& b){return {a.ff/b.ff,a.ss/b.ss};}
template<typename T> inline void maxs(T& x,const T& y){return void(x=max(x,y));}
template<typename T> inline void mins(T& x,const T& y){return void(x=min(x,y));}
template<typename T> inline void gcds(T& x,const T& y){return void(x=gcd(x,y));}
template<typename T> inline void lcms(T& x,const T& y){return void(x=lcm(x,y));}
template<typename T,typename T2>inline ostream& operator<<(ostream& os, const pair<T,T2>& p){
    os<<"["<<p.ff<<","<<p.ss<<"]";
    return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const vector<T>& a) {
    for(const T& _:a)os<<_<<' ';
    return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const vector<vector<T>>& a) {
    for(const vector<T>& _:a)os<<_<<endl;
    return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const set<T>& a) {
    for(const T& _:a)os<<_<<' ';
    return os;
}
template<typename T,typename T2>inline ostream& operator<<(ostream& os,const map<T,T2>& a) {
    for(const auto& _:a)os<<_<<' ';
    return os;
}
template<typename T,typename T2>inline ostream& operator<<(ostream& os,const unordered_map<T,T2>& a) {
    for(const auto& _:a)os<<_<<' ';
    return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const queue<T>& b) {
    queue<T> a=b;
    while(a.size()){
        os<<a.front()<<" ";
        a.pop();
    }
    return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const stack<T>& b) {
    stack<T> a=b;
    while(a.size()){
        os<<a.top()<<" ";
        a.pop();
    }
    return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const priority_queue<T>& b) {
    priority_queue<T> a=b;
    while(a.size()){
        os<<a.top()<<" ";
        a.pop();
    }
    return os;
}
template<typename T>inline ostream& operator<<(ostream& os,const priority_queue<T,vector<T>,greater<T>>& b) {
    priority_queue<T,vector<T>,greater<T>> a=b;
    while(a.size()){
        os<<a.top()<<" ";
        a.pop();
    }
    return os;
}
template<typename T,typename T2>inline istream& operator>>(istream& is,pair<T,T2>& p){
    is>>(p.ff)>>(p.ss);
    return is;
}
template<typename T>inline istream& operator>>(istream& is,vector<T>& a) {
    for(T& _:a)is>>_;
    return is;
}
inline void print(){cout<<endl;}
template<typename... Args>
inline void print(const Args&... args){
    ((cout<<args<<' '),...)<<endl;
}
inline void input(){}
template<typename... Args>
inline void input(Args&... args){
    (cin>>...>>args);
}
#ifdef ONLINE_JUDGE
template<typename... Args>
inline void debug(const Args&... args){
    return void("59");
}
#else
inline void debug(){cerr<<endl;}
template<typename... Args>
inline void debug(const Args&... args){
    ((cerr<<args<<' '),...)<<endl;
}
#endif
inline void yn(bool b){
    if(b)yes;
    else no;
}
#define ASSERT(condition, message)\
if(condition){\
    cerr<<"Assertion failed: "<<message<<" at "<<__FILE__<<":"<<to_string(__LINE__)<<endl;\
    abort();\
}
///////////////////////////////////////////////////////////////////
constexpr int N=2e5+5;
constexpr int A=1e9+5;
constexpr int MOD=1e9+7;
constexpr i32 INF=INT32_MAX;
constexpr ll  INFL=INT64_MAX;
constexpr int BLOCK=320;
constexpr ldouble EPS=1e-9;
constexpr int MAXQUERY=100;
constexpr int dx[4]={-1,0,1,0};
constexpr int dy[4]={0,1,0,-1};
mt19937 mt(clock());
///////////////////////////////////////////////////////////////////
int n,m,k,t,a,b,x,y,w,ans;
vi v,adj[N];
str s,q;

inline void subtask1(){
    for(char c:s)if(c=='0')return print(-1);
    print(0);
}
inline void subtask2(){
    int cnt=0;
    for(char c:s)cnt+=(c=='0');
    if(2*cnt-1>n)return print(-1);
    vci v;
    for(char c:s){
        if(v.size() && v.back().ff==c)v.back().ss++;
        else v.pb({c,1});
    }
    int cnt2=0;
    for(int i=0;i<v.size();i++){
        if(v[i].ff=='0')cnt2++;
    }
    return print(cnt-cnt2);
}
inline void subtask3(){
    vci v;
    for(char c:s){
        if(v.size() && v.back().ff==c)v.back().ss++;
        else v.pb({c,1});
    }
    int cnt=0,cnt2=0;
    for(int i=0;i<v.size();i++){
        if(i!=0 && v[i].ff=='1')cnt2++;
        if(i!=v.size()-1 && v[i].ff=='0')cnt++;
    }
    return print(min(cnt,cnt2));
}
inline void subtask4(){
    ASSERT(59,"no subtask 4");
    int cnt=0;
    for(char c:s)cnt+=(c=='1');
    if(n>3*cnt+2)return print(-1);
    vci v;
    for(char c:s){
        if(v.size() && v.back().ff==c)v.back().ss++;
        else v.pb({c,1});
    }
    int cnt2=0;
    for(int i=0;i<int(v.size());i++){
        if(v[i].ff=='0' && v[i].ss>2)cnt2++;
    }
    return print(cnt2);
}
inline void subtask5(){
    vci v;
    for(char c:s){
        if(v.size() && v.back().ff==c)v.back().ss++;
        else v.pb({c,1});
    }
    int cnt=0;
    for(int i=0;i<int(v.size())-1;i++){
        if(v[i].ff=='0' && v[i].ss>1)cnt++;
    }
    return print(cnt);
}
inline void subtask6(){
    vci v;
    for(char c:s){
        if(v.size() && v.back().ff==c)v.back().ss++;
        else v.pb({c,1});
    }
    int ans=0,cnt=0;
    for(int i=1;i<int(v.size())-1;i++){
        if(v[i].ff=='1'){
            if(v[i].ss>1)ans+=(cnt+1)/2,cnt=0;
            else cnt++;
        }
    }
    ans+=(cnt+1)/2,cnt=0;
    return print(ans);
}
inline void subtask7(){
    for(char& c:s)c='0'+'1'-c;
    for(char& c:q)c='0'+'1'-c;
    reverse(all(s));
    reverse(all(q));
    ASSERT(q!="001","subtask 7 fail");
    subtask5();
}
inline void solve(void){
    input(s,q);
    n=s.size();
    m=q.size();
    if(n<m)return print(0);
    if(q[0]=='1'){
        for(char& c:s)c='0'+'1'-c;
        for(char& c:q)c='0'+'1'-c;
    }
    str q=::q;
    if(q=="0")  subtask1();
    if(q=="00") subtask2();
    if(q=="01") subtask3();
    if(q=="000")subtask4();
    if(q=="001")subtask5();
    if(q=="010")subtask6();
    if(q=="011")subtask7();
}
signed main(void){
    int start=clock();
    fastio;
    //usacoio("59");
    int _testcase=1;
    //cin>>_testcase;
    while(_testcase--)solve();
    debug("Time elapsed:",(clock()-start)/uint64_t(1e6),"ms");
}

Compilation message

Main.cpp: In function 'void subtask2()':
Main.cpp:219:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long int'} and 'std::vector<std::pair<char, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
Main.cpp: In function 'void subtask3()':
Main.cpp:231:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long int'} and 'std::vector<std::pair<char, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  231 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
Main.cpp:233:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long int'} and 'std::vector<std::pair<char, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |         if(i!=v.size()-1 && v[i].ff=='0')cnt++;
      |            ~^~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 4 ms 4956 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 3 ms 5464 KB Output is correct
5 Correct 3 ms 5512 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 3 ms 5508 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 7 ms 9496 KB Output is correct
9 Correct 6 ms 7512 KB Output is correct
10 Correct 5 ms 7512 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 3 ms 5508 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 7 ms 9496 KB Output is correct
9 Correct 6 ms 7512 KB Output is correct
10 Correct 5 ms 7512 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct
12 Correct 3 ms 4996 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 2 ms 4956 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 3 ms 4952 KB Output is correct
18 Correct 3 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 3 ms 5468 KB Output is correct
21 Correct 3 ms 5468 KB Output is correct
22 Correct 8 ms 9552 KB Output is correct
23 Correct 6 ms 7512 KB Output is correct
24 Correct 5 ms 7512 KB Output is correct
25 Correct 3 ms 4952 KB Output is correct
26 Correct 3 ms 5468 KB Output is correct
27 Correct 6 ms 7512 KB Output is correct
28 Correct 3 ms 5468 KB Output is correct
29 Correct 9 ms 7508 KB Output is correct
30 Correct 4 ms 5468 KB Output is correct
31 Correct 6 ms 7456 KB Output is correct
32 Correct 8 ms 7304 KB Output is correct
33 Correct 3 ms 4956 KB Output is correct
34 Correct 2 ms 4956 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4952 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 4 ms 5468 KB Output is correct
9 Correct 6 ms 7512 KB Output is correct
10 Correct 6 ms 7508 KB Output is correct
11 Correct 7 ms 7444 KB Output is correct
12 Correct 9 ms 9496 KB Output is correct
13 Correct 7 ms 9556 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 5160 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 3 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 4 ms 5468 KB Output is correct
11 Correct 3 ms 5468 KB Output is correct
12 Correct 6 ms 7512 KB Output is correct
13 Correct 6 ms 7512 KB Output is correct
14 Correct 6 ms 7512 KB Output is correct
15 Correct 7 ms 9556 KB Output is correct
16 Correct 7 ms 9552 KB Output is correct
17 Incorrect 6 ms 7512 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4952 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 4 ms 5468 KB Output is correct
9 Correct 6 ms 7512 KB Output is correct
10 Correct 6 ms 7508 KB Output is correct
11 Correct 7 ms 7444 KB Output is correct
12 Correct 9 ms 9496 KB Output is correct
13 Correct 7 ms 9556 KB Output is correct
14 Correct 3 ms 4956 KB Output is correct
15 Correct 3 ms 4956 KB Output is correct
16 Correct 3 ms 4956 KB Output is correct
17 Correct 3 ms 5160 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 3 ms 4956 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 3 ms 4956 KB Output is correct
22 Correct 2 ms 4956 KB Output is correct
23 Correct 4 ms 5468 KB Output is correct
24 Correct 3 ms 5468 KB Output is correct
25 Correct 6 ms 7512 KB Output is correct
26 Correct 6 ms 7512 KB Output is correct
27 Correct 6 ms 7512 KB Output is correct
28 Correct 7 ms 9556 KB Output is correct
29 Correct 7 ms 9552 KB Output is correct
30 Incorrect 6 ms 7512 KB Output isn't correct
31 Halted 0 ms 0 KB -