Submission #771073

#	Time	Username	Problem	Language	Result	Execution time	Memory
771073		davitmarg	Crossing (JOI21_crossing)	C++17	26 / 100	7030 ms	28620 KiB

Main

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <random>
#include <chrono>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair    
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 500005;


string crossing(string a, string b)
{
    string s = a;
    for (int i = 0; i < a.length(); i++)
    {
        if (a[i] == b[i])
            continue;
        s[i] = '0' + ((a[i] - '0') ^ (b[i] - '0'));
    }
    return s;
}

string norm(string s)
{
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'J')
            s[i] = '1';
        else if(s[i] == 'O')
			s[i] = '2';
		else
			s[i] = '3';
    }
    return s;
}

int n, q;
string s[N];
map<LL, bool> used;

LL prime = 271;
LL pr[N];

void hashInit()
{
    pr[0] = 1;
    for(int i = 1; i <= n; i++)
		pr[i] = (pr[i - 1] * prime) % mod;
}

LL getHash(string s)
{
	LL h = 0;
	for(int i = 0; i < s.length(); i++)
        h = (h + ((LL)(s[i] - '0') + 1ll) * pr[i]) % mod;
	return h;
}

void solve()
{
    cin >> n;
    cin >> s[1] >> s[2] >> s[3];
    s[1] = norm(s[1]);
    s[2] = norm(s[2]);
    s[3] = norm(s[3]);

    hashInit();

    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            for (int k = 1; k <= 3; k++)
                used[getHash(crossing(crossing(s[i], s[j]), s[k]))] = 1;

    cin >> q;

    string t;
    cin >> t;
    if (used[getHash(norm(t))])
		cout << "Yes\n";
	else
		cout << "No\n";

    for (int i = 1; i <= q; i++)
    {
        int l, r;
        char c;
        cin>>l>>r>>c;
        for(int j = l - 1; j <= r - 1; j++)
            t[j] = c;

        if (used[getHash(norm(t))])
            cout << "Yes\n";
		else
			cout << "No\n";
    }
}


int main()
{
    fastIO;
    int T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }

    return 0;
}

/*


*/

Compilation message (stderr)

Main.cpp: In function 'std::string crossing(std::string, std::string)':
Main.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < a.length(); i++)
      |                     ~~^~~~~~~~~~~~
Main.cpp: In function 'std::string norm(std::string)':
Main.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i = 0; i < s.length(); i++)
      |                     ~~^~~~~~~~~~~~
Main.cpp: In function 'long long int getHash(std::string)':
Main.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i = 0; i < s.length(); i++)
      |                 ~~^~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 0 / 23
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51