Cod sursa(job #1826815)

Utilizator radu_uniculeu sunt radu radu_unicul Data 10 decembrie 2016 22:05:34
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int mod1=1e9+3,mod2=1e9+7;
vector<pair<int,int> > v1,v2,q;
char sir[3*1024*1024];

void solve(char sir[],vector<pair<int,int> > &v,int baza)
{
    int n=strlen(sir);
    q.clear();
    v.clear();
    q.push_back({0,0});
    for(int i=0;i<n;i++)
        if(sir[i]=='d') q.pop_back();
        else if(sir[i]=='t') v.push_back(q.back());
        else if('0'<=sir[i] && sir[i]<='9')
        {
            pair<int,int> a=q.back();
            a.first=(1LL*a.first*baza+sir[i]-'0')%mod1;
            a.second=(1LL*a.second*baza+sir[i]-'0')%mod2;
            q.push_back(a);
        }
}

int main()
{
    freopen("twosets.in", "r", stdin);
    freopen("twosets.out", "w", stdout);
    int t;
    for(scanf("%d",&t);t;t--)
    {
        scanf("\n%s",sir);
        solve(sir,v1,2);
        sort(v1.begin(),v1.end());
        scanf("\n%s",sir);
        solve(sir,v2,10);
        sort(v2.begin(),v2.end());
        if(v1.size()!=v2.size()) printf("0\n");
        else
        {
            int ok=1;
            for(int i=0;i<v1.size();i++)
                if(v1[i]!=v2[i]) {ok=0;break;}
            printf("%d\n",ok);
        }
    }
    return 0;
}