QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#510274#9158. 分数ninjadoggy1234#0 1554ms115012kbC++203.8kb2024-08-09 01:08:192024-08-09 01:08:20

Judging History

你现在查看的是最新测评结果

  • [2024-08-09 01:08:20]
  • 评测
  • 测评结果:0
  • 用时:1554ms
  • 内存:115012kb
  • [2024-08-09 01:08:19]
  • 提交

answer

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <cstring>

#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <string>
#include <map>
#include <unordered_map>
#include <vector>
#include <functional>
#include <numeric>

#define int long long
#define FOR(a,b) for(int a = 0; a < b; a++)
#define All(vec) vec.begin(),vec.end()

using std::string;
using std::vector;
using std::pair;
using std::cin;
using std::cout;
const int oo = 3074457345618258602LL;

std::stringstream out;

template<class T> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0;
}
template<class T> bool ckmin(T& a, const T& b) {
	return a > b ? a = b, 1 : 0;
}

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
	static_assert(D >= 1, "Vector dimension must be greater than zero!");
	template<typename U, typename... Args>
	Vec(U n = U(), Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
	}
	template<typename... Args>
	Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
	}
};
template<typename T>
struct Vec<1, T> : public vector<T> {
	template<typename... Args>
	Vec(Args... args) : vector<T>(args...) {
	}
	Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {
	}
};

const bool kReadTestCases = 0;
const bool kLocalRun = 0;
const bool kBruteSolve = 0;
struct Fraction {
	int num, denom;


};
struct Solution {

	void ReadInput() {
	}

	void Solve(std::stringstream& out) {
		int N, M;
		cin >> N >> M;
		std::deque<pair<int, int>> q;
		std::set<pair<int, int>> vis;
		int ans = 0;
		auto Add = [&](int num, int denom) {
			if (num <= 0)return;
			if (num * 2 > denom && num < 2 * denom) {
				return;
			}
			int gcd = std::gcd(num, denom);
			num /= gcd;
			denom /= gcd;
			auto p = std::make_pair(num, denom);
			if (vis.insert(p).second) {
				if (num <= N && denom <= M) {
					ans++;
				}
				q.push_back(p);
			}
			};
		Add(1, 2);
		FOR(iter, 1000000) {
			auto [num, denom] = q.front(); q.pop_front();
			Add(denom, num);
			Add(num + 2 * denom, denom);
			Add(num - 2 * denom, denom);
		}
		out << ans << "\n";
	}

	void SolveBrute(std::stringstream& out) {

	}
	void GenInput() {

	}
	void PrintInput() {

	}

	inline vector<int> ReadVec(int N) {
		vector<int> vec(N);
		FOR(i, N) {
			cin >> vec[i];
		}
		return vec;
	}

	inline string Stringify(vector<int>& arr) {
		std::stringstream ss;
		FOR(i, arr.size()) {
			ss << arr[i] << " \n"[i == arr.size() - 1];
		}
		return ss.str();
	}
};


void RunLocal() {
	srand(time(NULL));
	int iter = 0;
	while (true) {
		if (++iter % 1000 == 0) {
			std::cout << iter << "\n";
		}
		Solution solution;
		solution.GenInput();
		std::stringstream ss1;
		std::stringstream ss2;
		solution.Solve(ss1);
		solution.SolveBrute(ss2);
		string ans = ss1.str();
		string ans_correct = ss2.str();
		if (ans != ans_correct) {
			solution.PrintInput();
			cout << "\n\n";
			cout << "Wrong answer:\n";
			cout << "---------------------------------------------------------\n";
			cout << ans << "\n";
			cout << "Correct answer:\n";
			cout << "---------------------------------------------------------\n";
			cout << ans_correct << "\n";
			break;
		}
	}
}

int32_t main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	if (kLocalRun) {
		RunLocal();
		return 0;
	}
	int tc = 1;
	if (kReadTestCases)std::cin >> tc;
	for (int _ = 1; _ <= tc; _++) {
		Solution solution;
		solution.ReadInput();
		if (kBruteSolve) {
			solution.SolveBrute(out);
		} else {
			solution.Solve(out);
		}
	}
	std::cout << out.str();
	std::cout.flush();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 0
Wrong Answer
time: 1440ms
memory: 114760kb

input:

99 99

output:

361

result:

wrong answer 1st numbers differ - expected: '406', found: '361'

Pretest #2:

score: 0
Wrong Answer
time: 1460ms
memory: 114884kb

input:

98 97

output:

361

result:

wrong answer 1st numbers differ - expected: '405', found: '361'

Pretest #3:

score: 0
Wrong Answer
time: 1472ms
memory: 114888kb

input:

99 96

output:

352

result:

wrong answer 1st numbers differ - expected: '396', found: '352'

Pretest #4:

score: 0
Wrong Answer
time: 1456ms
memory: 114760kb

input:

995 977

output:

6488

result:

wrong answer 1st numbers differ - expected: '11153', found: '6488'

Pretest #5:

score: 0
Wrong Answer
time: 1445ms
memory: 114672kb

input:

991 990

output:

6531

result:

wrong answer 1st numbers differ - expected: '11220', found: '6531'

Pretest #6:

score: 0
Wrong Answer
time: 1472ms
memory: 114784kb

input:

976 968

output:

6357

result:

wrong answer 1st numbers differ - expected: '10900', found: '6357'

Pretest #7:

score: 0
Wrong Answer
time: 1464ms
memory: 114988kb

input:

7602 7864

output:

70247

result:

wrong answer 1st numbers differ - expected: '215706', found: '70247'

Pretest #8:

score: 0
Wrong Answer
time: 1448ms
memory: 115012kb

input:

7959 7735

output:

71432

result:

wrong answer 1st numbers differ - expected: '220256', found: '71432'

Pretest #9:

score: 0
Wrong Answer
time: 1433ms
memory: 114688kb

input:

7878 7863

output:

71578

result:

wrong answer 1st numbers differ - expected: '221162', found: '71578'

Pretest #10:

score: 0
Wrong Answer
time: 1491ms
memory: 114992kb

input:

7788 7658

output:

70197

result:

wrong answer 1st numbers differ - expected: '215323', found: '70197'

Pretest #11:

score: 0
Wrong Answer
time: 1418ms
memory: 114780kb

input:

95399 99767

output:

740351

result:

wrong answer 1st numbers differ - expected: '8285295', found: '740351'

Pretest #12:

score: 0
Wrong Answer
time: 1442ms
memory: 114992kb

input:

98051 99642

output:

748641

result:

wrong answer 1st numbers differ - expected: '8439713', found: '748641'

Pretest #13:

score: 0
Wrong Answer
time: 1465ms
memory: 114816kb

input:

95624 96007

output:

732421

result:

wrong answer 1st numbers differ - expected: '8068127', found: '732421'

Pretest #14:

score: 0
Wrong Answer
time: 1443ms
memory: 114980kb

input:

99208 98047

output:

748592

result:

wrong answer 1st numbers differ - expected: '8412610', found: '748592'

Pretest #15:

score: 0
Wrong Answer
time: 1495ms
memory: 114912kb

input:

997417 967722

output:

1617463

result:

wrong answer 1st numbers differ - expected: '229917323', found: '1617463'

Pretest #16:

score: 0
Wrong Answer
time: 1452ms
memory: 114772kb

input:

987807 956529

output:

1617340

result:

wrong answer 1st numbers differ - expected: '226426912', found: '1617340'

Pretest #17:

score: 0
Wrong Answer
time: 1474ms
memory: 114756kb

input:

971654 984345

output:

1617149

result:

wrong answer 1st numbers differ - expected: '228363805', found: '1617149'

Pretest #18:

score: 0
Wrong Answer
time: 1461ms
memory: 114776kb

input:

7892259 7983727

output:

1618035

result:

wrong answer 1st numbers differ - expected: '4647501224', found: '1618035'

Pretest #19:

score: 0
Wrong Answer
time: 1449ms
memory: 114712kb

input:

7937869 29796968

output:

1618035

result:

wrong answer 1st numbers differ - expected: '15197555613', found: '1618035'

Pretest #20:

score: 0
Wrong Answer
time: 1473ms
memory: 114700kb

input:

29717543 29510173

output:

1618035

result:

wrong answer 1st numbers differ - expected: '30904211576', found: '1618035'


Final Tests

Test #1:

score: 0
Wrong Answer
time: 1447ms
memory: 114760kb

input:

96 98

output:

352

result:

wrong answer 1st numbers differ - expected: '396', found: '352'

Test #2:

score: 0
Wrong Answer
time: 1475ms
memory: 114712kb

input:

100 99

output:

362

result:

wrong answer 1st numbers differ - expected: '408', found: '362'

Test #3:

score: 0
Wrong Answer
time: 1475ms
memory: 114760kb

input:

99 99

output:

361

result:

wrong answer 1st numbers differ - expected: '406', found: '361'

Test #4:

score: 0
Wrong Answer
time: 1438ms
memory: 114780kb

input:

963 951

output:

6223

result:

wrong answer 1st numbers differ - expected: '10634', found: '6223'

Test #5:

score: 0
Wrong Answer
time: 1453ms
memory: 114704kb

input:

958 974

output:

6302

result:

wrong answer 1st numbers differ - expected: '10795', found: '6302'

Test #6:

score: 0
Wrong Answer
time: 1434ms
memory: 114776kb

input:

966 990

output:

6412

result:

wrong answer 1st numbers differ - expected: '11003', found: '6412'

Test #7:

score: 0
Wrong Answer
time: 1461ms
memory: 115008kb

input:

7958 7947

output:

72463

result:

wrong answer 1st numbers differ - expected: '224482', found: '72463'

Test #8:

score: 0
Wrong Answer
time: 1407ms
memory: 114712kb

input:

7623 7730

output:

69697

result:

wrong answer 1st numbers differ - expected: '213444', found: '69697'

Test #9:

score: 0
Wrong Answer
time: 1432ms
memory: 114712kb

input:

7845 7783

output:

71059

result:

wrong answer 1st numbers differ - expected: '218916', found: '71059'

Test #10:

score: 0
Wrong Answer
time: 1452ms
memory: 114976kb

input:

7881 7773

output:

71167

result:

wrong answer 1st numbers differ - expected: '219451', found: '71167'

Test #11:

score: 0
Wrong Answer
time: 1478ms
memory: 114708kb

input:

99414 98698

output:

750647

result:

wrong answer 1st numbers differ - expected: '8465217', found: '750647'

Test #12:

score: 0
Wrong Answer
time: 1483ms
memory: 114856kb

input:

98249 96148

output:

741248

result:

wrong answer 1st numbers differ - expected: '8237486', found: '741248'

Test #13:

score: 0
Wrong Answer
time: 1509ms
memory: 114748kb

input:

99003 96832

output:

745057

result:

wrong answer 1st numbers differ - expected: '8324931', found: '745057'

Test #14:

score: 0
Wrong Answer
time: 1461ms
memory: 115008kb

input:

98266 96030

output:

740993

result:

wrong answer 1st numbers differ - expected: '8231065', found: '740993'

Test #15:

score: 0
Wrong Answer
time: 1451ms
memory: 114816kb

input:

968207 958885

output:

1617136

result:

wrong answer 1st numbers differ - expected: '223522215', found: '1617136'

Test #16:

score: 0
Wrong Answer
time: 1446ms
memory: 114756kb

input:

959846 998397

output:

1617034

result:

wrong answer 1st numbers differ - expected: '228770873', found: '1617034'

Test #17:

score: 0
Wrong Answer
time: 1447ms
memory: 114740kb

input:

965821 972280

output:

1617115

result:

wrong answer 1st numbers differ - expected: '225359210', found: '1617115'

Test #18:

score: 0
Wrong Answer
time: 1419ms
memory: 114980kb

input:

7855098 7962479

output:

1618035

result:

wrong answer 1st numbers differ - expected: '4622947400', found: '1618035'

Test #19:

score: 0
Wrong Answer
time: 1554ms
memory: 115008kb

input:

7841076 29648718

output:

1618035

result:

wrong answer 1st numbers differ - expected: '15040798710', found: '1618035'

Test #20:

score: 0
Wrong Answer
time: 1451ms
memory: 114816kb

input:

29365129 29012208

output:

1618035

result:

wrong answer 1st numbers differ - expected: '30267839959', found: '1618035'