Cod sursa(job #1709608)

Utilizator cpitting_llamasRotaru Tanase Gherghina cpitting_llamas Data 28 mai 2016 13:03:22
Problema Consecutive Scor 0
Compilator cpp Status done
Runda ONIS 2016 - Runda - 2 - ACM ICPC Romanian Programming Contest Marime 1.65 kb
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <string>
#include <limits>
#include <vector>
#include <bitset>
#include <utility>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define MOD 10001 // daca e nevoie de mod
#define oo 2000000000
#define ooLL (1LL<<60)
#define LSB(x) (x&(-x)) // least significat bit of
#define eps 0.00001

typedef long long ull;
typedef long double ld;

int main()
{
	std::ifstream cin("consecutive.in");
	std::ofstream cout("consecutive.out");
	int test_count;
	cin >> test_count;
	for (auto test_idx = 0; test_idx < test_count; ++test_idx) {
		int N;
		cin >> N;
		int count = 0;
		std::vector<std::pair<int, int> > intervals;

		int lmax = 0;
		for (; (lmax * (lmax + 1) / 2) < N; lmax++);
		//std::cout << "lmax = " << lmax << "\n";
		for (int l = 1; l <= lmax; ++l) {
			int off_low = 0;
			int off_high = N / 2;
			//std::cout << "checking substring of length = " << l << "\n";
			while(off_low < off_high) {
				int off_mid = off_low + (off_high - off_low) / 2;
				//std::cout << "trying " << off_mid << " as offset \n";
				int ttloff = off_mid * l;

				if (ttloff + (l * (l + 1) / 2) == N) {
					//std::cout << "Found "
					intervals.push_back(std::make_pair(off_mid + 1, off_mid + l));
					count++;
					break;
				} else if (ttloff + (l * (l + 1) / 2) > N) {
					off_high = off_mid;
				} else {
					off_low = off_mid + 1;
				}
			}
		}

		cout << count << "\n";
		for (uint i = 0; i < intervals.size(); ++i) {
			cout << intervals[i].first << " " << intervals[i].second << "\n";
		}
	}

	cin.close();
	cout.close();
	return 0;
}