oj.uz

Submission #721205

# Submission time Handle Problem Language Result Execution time Memory
721205 2023-04-10T13:48:36 Z vjudge1 Zamjena (COCI18_zamjena) C++17
70 / 70
 174 ms 7520 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ld long double
#define ll long long
#define S second
#define F first

using namespace __gnu_pbds;
using namespace std;

typedef tree<long long, null_type, less_equal<long long>,
    rb_tree_tag, tree_order_statistics_node_update> Tree;

const ll INF = 9223372036854775807LL;
const ll inf = 2147483647;
const ll MAXN = 200010;
const ll MOD = 1e9 + 7;
const ld PI = acos(-1);
const ll NROOT = 320; 

ll binpow(ll a, ll b) {
  ll res = 1;
  for (;b; b /= 2, a *= a, a %= MOD)
    if (b & 1) res *= a, res %= MOD;
  return res % MOD;
}

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}
ll invmod(ll a) {return binpow(a, MOD - 2);}

ll stroi(string s) {
  ll ans = 0;
  for (ll i = 0; i < s.size(); i ++) {
    ans *= 10;
    ans += (s[i] - '0');
  }
  return ans;
}

bool is(string b) {
  if (b[0] >= 'a' && b[0] <= 'z') {
    return 1;
  }
  return 0;
}

bool comp(ll n, vector<string> &a, vector<string> &b, map<string, ll> &v) {
  for (ll i = 1; i <= n; i ++) {
    if (!is(a[i]) && !is(b[i])) {
      if (a[i] != b[i]) {
        return 0;
      } 
    } else if (is(a[i])) {
      if (is(b[i])) {
        if (v[a[i]] != -1) {
          if (v[b[i]] == -1) v[b[i]] = v[a[i]];
          else if (v[b[i]] != v[a[i]]) {
            return 0;
          }
        } else {
          if (v[b[i]] != -1) v[a[i]] = v[b[i]];
        }
      } else {
        if (v[a[i]] != -1 && v[a[i]] != stroi(b[i])) {
          return 0;
        } else if (v[a[i]] == -1) {
          v[a[i]] = stroi(b[i]);
        }
      }
    } else if (is(b[i])) {
      if (v[b[i]] == -1) v[b[i]] = stroi(a[i]);
      else if (v[b[i]] != -1 && v[b[i]] != stroi(a[i])) {
        return 0;
      }
    }
  }
  return 1;
}

int32_t main () {
  ios_base::sync_with_stdio(false); 
  cin.tie(nullptr);

  ll n; cin >> n;

  vector<string> a(n + 1), b(n + 1);
  map<string, ll> v;

  for (ll i = 1; i <= n; i ++) {
    cin >> a[i];
    if (is(a[i])) {
      v[a[i]] = -1;
    }
  }
  for (ll i = 1; i <= n; i ++) {
    cin >> b[i];
    if (is(b[i])) {
      v[b[i]] = -1;
    }
  }

  comp(n, a, b, v);
  comp(n, a, b, v);
  comp(n, a, b, v);
  bool res = comp(n, a, b, v);

  /*for (ll i = 1; i <= n; i ++) {
    if (is(a[i])) cout << v[a[i]] << " ";
    else cout << a[i] << " ";
  } cout << "\n";
  for (ll i = 1; i <= n; i ++) {
    if (is(b[i])) cout << v[b[i]] << " ";
    else cout << b[i] << " ";
  } cout << "\n";*/

  if (res) cout << "DA\n";
  else cout << "NE\n";

  return 0;
}

Compilation message

zamjena.cpp: In function 'long long int stroi(std::string)':
zamjena.cpp:35:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (ll i = 0; i < s.size(); i ++) {
      |                  ~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 10 ms 596 KB Output is correct
6 Correct 7 ms 596 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1364 KB Output is correct
2 Correct 60 ms 2516 KB Output is correct
3 Correct 62 ms 4076 KB Output is correct
4 Correct 61 ms 5068 KB Output is correct
5 Correct 173 ms 7520 KB Output is correct
6 Correct 174 ms 5368 KB Output is correct