Submission #5552821


Source Code Expand

Copy
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, Y) for (int(X) = 0; (X) < (Y); ++(X))
#define rrep(X, Y) for (int(X) = (Y)-1; (X) >= 0; --(X))
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

ll rev(ll x) {
  stringstream ss;
  ss << x;

  string str;
  ss >> str;

  reverse(str.begin(), str.end());

  ss.clear();

  ss << str;
  ss >> x;
  return x;
}

void solve(long long N, long long M) {
  map<pll, ll> checked; // ll-> 0: 不明, 1: 無限, 2: 無限ではない
  for (ll n = 1; n <= N; n++) {
    for (ll m = 1; m <= M; m++) {
      if (checked.find(mp(n, m)) != checked.end()) {
        continue;
      }

      ll nRev = n;
      ll mRev = m;

      queue<pll> que;
      while (true) {
        if (nRev == 0 || mRev == 0) {
          while (!que.empty()) {
            auto p = que.front();
            checked[p] = 2;
            que.pop();
          }
          break;
        }

        if (checked.find(mp(nRev, mRev)) != checked.end()) {
          ll i = checked[mp(nRev, mRev)];
          if (checked[mp(nRev, mRev)] == 0) {
            i = 1;
          }

          while (!que.empty()) {
            auto p = que.front();
            checked[p] = i;
            que.pop();
          }
          break;
        }

        checked[mp(nRev, mRev)] = 0;
        checked[mp(mRev, nRev)] = 0;
        que.push(mp(nRev, mRev));
        que.push(mp(mRev, nRev));

        if (nRev < mRev) {
          nRev = rev(nRev);
        } else {
          mRev = rev(mRev);
        }

        if (nRev < mRev) {
          mRev -= nRev;
        } else {
          nRev -= mRev;
        }
      }
    }
  }

  ll ans = 0;
  for (ll n = 1; n <= N; n++) {
    for (ll m = 1; m <= M; m++) {
      if (checked[mp(n, m)] == 1) {
        // print(n << "," << m << ":" << checked[mp(n, m)]);
        ans++;
      }
    }
  }
  print(ans);
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  solve(N, M);
  return 0;
}

Submission Info

Submission Time
Task D - うほょじご
User righttoleft1134
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2565 Byte
Status
Exec Time 1474 ms
Memory 62848 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:123:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &N);
                    ^
./Main.cpp:125:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &M);
                    ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 400 / 400 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 1456 ms 62848 KB
02.txt 3 ms 384 KB
03.txt 1373 ms 50176 KB
04.txt 11 ms 896 KB
05.txt 12 ms 896 KB
06.txt 1 ms 256 KB
07.txt 1 ms 256 KB
08.txt 1474 ms 62592 KB
09.txt 60 ms 3840 KB
10.txt 1185 ms 51840 KB
11.txt 1472 ms 62720 KB
12.txt 3 ms 384 KB
13.txt 4 ms 512 KB
14.txt 500 ms 23424 KB
15.txt 2 ms 256 KB
16.txt 640 ms 28544 KB
s1.txt 1 ms 256 KB
s2.txt 2 ms 384 KB
s3.txt 148 ms 8192 KB