CSES - Aalto Competitive Programming 2024 - wk1 - Mon

CSES - Aalto Competitive Programming 2024 - wk1 - Mon - Results

Submission details
Task:	Babaza Game
Sender:	AleksandrPolitov
Submission time:	2024-09-02 17:44:34 +0300
Language:	C++ (C++20)
Status:	READY
Result:	WRONG ANSWER

Test results
test	verdict
#1	ACCEPTED	details
#2	ACCEPTED	details
#3	ACCEPTED	details
#4	ACCEPTED	details
#5	WRONG ANSWER	details
#6	ACCEPTED	details
#7	ACCEPTED	details
#8	ACCEPTED	details
#9	ACCEPTED	details
#10	ACCEPTED	details
#11	ACCEPTED	details
#12	ACCEPTED	details
#13	ACCEPTED	details
#14	ACCEPTED	details

Compiler report

input/code.cpp:11:19: warning: overflow in conversion from 'double' to 'int' changes value from '4.0e+18' to '2147483647' [-Woverflow]
   11 | const int LLINF = 4e18; // 4*10^18 is < 2^63-1
      |                   ^~~~
input/code.cpp: In function 'bool ok(std::string&)':
input/code.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < s.size()-1; i++) {
      |                     ~~^~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for(int i=a; i< (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
 
const int INF = 1e9; // 10^9 = 1B is < 2^31-1
const int LLINF = 4e18; // 4*10^18 is < 2^63-1
const double EPS = 1e-9;
const ll MOD = 1e9+7;
 
vector<string> ans(1000);
 
 
 
bool ok(string &s) {
    for (int i = 0; i < s.size()-1; i++) {
        if(s[i]==s[i+1]) return false;
    }
    return true;
}
 
std::set<char> nonUsed;
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    
    string a, b; std::cin >> a >> b;
    int n=a.size();
 
    for (int i = 0; i < 26; i++) {
        nonUsed.insert((char)('A'+i));
    }
 
 
 
    for (int i = 0; i < a.size(); i++) {
        nonUsed.erase(a[i]);
        nonUsed.erase(b[i]);
    }
    
 
    // None
    if(a==b) {
        std::cout << a << std::endl;
        return 0;
    }
 
    // even
    {
        bool status=true;
        string tmp=a;
        for (int i = 0; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                tmp[i]=b[i];
            }
        }
        if(!ok(tmp) || tmp!=b) status=false;
 
        if(status) {
            std::cout << a << std::endl;
            std::cout << b << std::endl;
            return 0;
        }
    }
 
    // odd
    {
        bool status=true;
        string tmp=a;
        for (int i = 1; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                tmp[i]=b[i];
            }
        }
        if(!ok(tmp) || tmp!=b) status=false;
 
        if(status) {
            std::cout << a << std::endl;
            std::cout << b << std::endl;
            return 0;
        }
    }
 
 
 
 
    // even -> odd
    {
        vector<string> res;
        res.pb(a);
        bool status=true;
        string tmp=a;
        for (int i = 0; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                tmp[i]=b[i];
            }
        }
        if(tmp!=res.back())
            res.pb(tmp);
 
        if(!ok(tmp)) status=false;
 
        for (int i = 1; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                tmp[i]=b[i];
            }
        }
        if(tmp!=res.back())
            res.pb(tmp);
 
        if(!ok(tmp)) status=false;
 
        if(b!=tmp) res.pb(b);
        
        if(status && res.back()==b && res.size()<ans.size()) {
            ans=res;
        }
    }
 
    // odd -> even
    {
        vector<string> res;
        res.pb(a);
        bool status=true;
        string tmp=a;
        for (int i = 1; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                tmp[i]=b[i];
            }
        }
        if(tmp!=res.back())
        res.pb(tmp);
 
        if(!ok(tmp)) status=false;
 
        for (int i = 0; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                tmp[i]=b[i];
            }
        }
        if(tmp!=res.back())
        res.pb(tmp);
 
        if(!ok(tmp)) status=false;
 
        
        if(b!=tmp) res.pb(b);
        if(status && res.back()==b && res.size()<ans.size()) {
            ans=res;
        }
    }
 
 
 
    // even -> odd -> even
    {
        vector<string> res;
        res.pb(a);
        bool status=true;
        string tmp=a;
 
        for (int i = 0; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                bool can=true;
                if(i+1<n) can&=tmp[i+1]!=b[i];
                if(i-1>=0) can&=tmp[i-1]!=b[i];
                if(can) {
                    tmp[i]=b[i];
                } else {
                    tmp[i]=*nonUsed.begin();
                }
            }
        }
        if(tmp!=res.back())
        res.pb(tmp);
        if(!ok(tmp)) status=false;
 
        for (int i = 1; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                bool can=true;
                if(i+1<n) can&=tmp[i+1]!=b[i];
                if(i-1>=0) can&=tmp[i-1]!=b[i];
                if(can) {
                    tmp[i]=b[i];
                } else {
                    tmp[i]=*nonUsed.begin();
                }
            }
        }
        if(tmp!=res.back()) res.pb(tmp);
        if(!ok(tmp)) status=false;
 
        for (int i = 0; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                bool can=true;
                if(i+1<n) can&=tmp[i+1]!=b[i];
                if(i-1>=0) can&=tmp[i-1]!=b[i];
                if(can) {
                    tmp[i]=b[i];
                } else {
                    tmp[i]=*nonUsed.begin();
                }
            }
        }
 
 
 
        if(tmp!=res.back()) res.pb(tmp);
        if(!ok(tmp)) status=false;
 
        
        
        if(status && res.back()==b && res.size()<ans.size()) {
            ans=res;
        }
    }
 
 
     // odd -> even -> odd
    {
        vector<string> res;
        res.pb(a);
        bool status=true;
        string tmp=a;
 
        for (int i = 1; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                bool can=true;
                if(i+1<n) can&=tmp[i+1]!=b[i];
                if(i-1>=0) can&=tmp[i-1]!=b[i];
                if(can) {
                    tmp[i]=b[i];
                } else {
                    tmp[i]=*nonUsed.begin();
                }
            }
        }
        if(tmp!=res.back())
        res.pb(tmp);
        if(!ok(tmp)) status=false;
 
        for (int i = 0; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                bool can=true;
                if(i+1<n) can&=tmp[i+1]!=b[i];
                if(i-1>=0) can&=tmp[i-1]!=b[i];
                if(can) {
                    tmp[i]=b[i];
                } else {
                    tmp[i]=*nonUsed.begin();
                }
            }
        }
        if(tmp!=res.back())
        res.pb(tmp);
        if(!ok(tmp)) status=false;
 
        for (int i = 1; i < n; i+=2) {
            if(tmp[i]!=b[i]) {
                bool can=true;
                if(i+1<n) can&=tmp[i+1]!=b[i];
                if(i-1>=0) can&=tmp[i-1]!=b[i];
                if(can) {
                    tmp[i]=b[i];
                } else {
                    tmp[i]=*nonUsed.begin();
                }
            }
        }
 
 
 
        if(tmp!=res.back())
        res.pb(tmp);
        if(!ok(tmp)) status=false;
 
        
        
        if(status && res.back()==b && res.size()<ans.size()) {
            ans=res;
        }
    }
 
    for(auto &w:ans) {
        std::cout << w << std::endl;
    }
 
 
 
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`A B` view save

correct output
`A B` view save

user output
`A B` view save

Test 2

Verdict: ACCEPTED

input
`BABAZA BACBCB` view save

correct output
`BABAZA BACACA BACBCB` view save

user output
`BABAZA BACACA BACBCB` view save

Test 3

Verdict: ACCEPTED

input
`AB BA` view save

correct output
`AB CB CA BA` view save

user output
`AB CB CA BA` view save

Test 4

Verdict: ACCEPTED

input
`ABC BCD` view save

correct output
`ABC DBD DCD BCD` view save

user output
`ABC EBD ECD BCD` view save

Test 5

Verdict: WRONG ANSWER

input
`AXYB CXYD` view save

correct output
`AXYB CXYD` view save

user output
`AXYB CXYB CXYD` view save

Test 6

Verdict: ACCEPTED

input
`LMIJLF PAQBMH` view save

correct output
`LMIJLF PMQJMF PAQBMH` view save

user output
`LMIJLF PMQJMF PAQBMH` view save

Test 7

Verdict: ACCEPTED

input
`PNIWLSLIH CRLVPUFHD` view save

correct output
`PNIWLSLIH CNLWPSFID CRLVPUFHD` view save

user output
`PNIWLSLIH CNLWPSFID CRLVPUFHD` view save

Test 8

Verdict: ACCEPTED

input
`ZDYIAVTKL ZJKVXGAUM` view save

correct output
`ZDYIAVTKL ZJYVAGTUL ZJKVXGAUM` view save

user output
`ZDYIAVTKL ZDKIXVAKM ZJKVXGAUM` view save

Test 9

Verdict: ACCEPTED

input
`FBIXISJH NXZIESMG` view save

correct output
`FBIXISJH NBZXESMH NXZIESMG` view save

user output
`FBIXISJH NBZXESMH NXZIESMG` view save

Test 10

Verdict: ACCEPTED

input
`OPGW QJIE` view save

correct output
`OPGW QPIW QJIE` view save

user output
`OPGW QPIW QJIE` view save

Test 11

Verdict: ACCEPTED

input
`DUKNPKQZBL NZPBMOEBIC` view save

correct output
`DUKNPKQZBL NUPNMKEZIL NZPBMOEBIC` view save

user output
`DUKNPKQZBL NUPNMKEZIL NZPBMOEBIC` view save

Test 12

Verdict: ACCEPTED

input
`ZWDTX HZOXI` view save

correct output
`ZWDTX HWOTI HZOXI` view save

user output
`ZWDTX HWOTI HZOXI` view save

Test 13

Verdict: ACCEPTED

input
`URJF ITIQ` view save

correct output
`URJF IRIF ITIQ` view save

user output
`URJF IRIF ITIQ` view save

Test 14

Verdict: ACCEPTED

input
`WYWBWU IRYVBA` view save

correct output
`WYWBWU WRWVWA IRYVBA` view save

user output
`WYWBWU WRWVWA IRYVBA` view save

Aalto Competitive Programming 2024 - wk1 - Mon

Babaza Game

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Tasks

Submissions (AleksandrPolitov)