#pragma once
/*
* STRICT.H version 0.3.1
* Library for validation of input data for the programming contest problems. Requires C++17.
* Copyright (c) Vladimir Yakovlev, 2011-2024
* http://acm.timus.ru/stricth
*/
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <regex>
#include <optional>
#if (_WIN32 || __WIN32__)
#include <fcntl.h>
#include <io.h>
#define ON_WINDOWS
#endif
// ==================================================== INTERFACE ====================================================
// Provides primitives for reading the input stream and strictly checking its validity.
// Example usage:
// Input in;
// int n = in.readInt(1, 50);
// in.readSpace();
// int m = in.readInt(1, 50);
// in.assert(n + m <= 50);
// in.readEoln();
// in.readEof();
class Input
{
FILE* m_file;
int c;
int line;
int pos;
void setBinaryMode();
void nextChar();
void assertDigit() const;
void init();
void parsePattern(const char* charPattern, bool valid[256]) const;
template<typename T>
void checkConstraints(const T&) const;
template<typename T, typename First, typename... Args>
void checkConstraints(const T& value, First&& first, Args&&... constraints) const;
public:
// Initializes reading from stdin.
Input();
// Initializes reading from a file.
Input(const char* fileName);
// Makes the class non-copyable.
Input(const Input&) = delete;
Input& operator=(const Input&) = delete;
~Input();
// Returns whether the next character is SPACE (ASCII 32).
bool isSpace() const;
// Returns whether the next character is whitespace (SPACE, TAB, EOLN).
bool isWhitespace() const;
// Returns whether the next character is EOLN (ASCII 13 for Unix, ASCII 13 10 for Windows).
bool isEoln() const;
// Returns whether the next character is EOF (end of file).
bool isEof() const;
// Returns whether the next character matches the pattern, e.g. "-_a-zA-Z". Note that this is NOT a regexp.
bool isChar(const char* charPattern) const;
// Reads the next character and checks that it equals to SPACE.
void readSpace();
// Reads the next characters while they are equal to SPACE.
void readZeroOrMoreSpaces();
// Reads the next character and checks that it equals to SPACE,
// then reads next characters while they are equal to SPACE.
void readOneOrMoreSpaces();
// Reads the next character and checks that it equals to EOLN (end of line).
void readEoln();
// Reads the next character and checks that it equals to SPACE or EOLN.
void readSpaceOrEoln();
// Reads the next character and checks that it equals to EOF (end of file).
void readEof();
// Reads and returns the next character (from 0 to 255).
int readChar();
// Reads and returns the next character (from 0 to 255).
// Checks that the character matches the pattern, e.g. "-_a-zA-Z". Note that this is NOT a regexp.
int readChar(const char* charPattern);
// Reads characters until the next whitespace or EOF. Checks that the result is non-empty.
std::string readToken();
// Reads characters until the next whitespace or EOF. Checks that the result is non-empty. Checks the length
// of the result and that its characters match the pattern, e.g. "-_a-zA-Z". Note that this is NOT a regexp.
// Checks the result with all provided constraint objects.
template<typename... Args>
std::string readToken(int minLength, int maxLength, const char* charPattern, Args&&... constraints);
// Reads characters until the next whitespace or EOF. Checks that the result is non-empty. Checks that the result
// matches the regexp, e.g. "[a-z]{1,10}". Checks the result with all provided constraint objects.
template<typename... Args>
std::string readToken(const std::string& regexp, Args&&... constraints);
// Reads characters until the next EOLN and skips the EOLN character.
std::string readLine();
// Reads characters until the next EOLN and skips the EOLN character. Checks the length of the result
// and that its characters match the pattern, e.g. "-_a-zA-Z". Note that this is NOT a regexp.
std::string readLine(int minLength, int maxLength, const char* charPattern);
// Reads characters until the next EOLN and skips the EOLN character. Checks that the result matches
// the regexp, e.g. "[a-z]{1,10}".
std::string readLine(const std::string& regexp);
// Reads a signed 32-bit integer, checks that it's well-formed and lies in the given range. Checks the result
// with all provided constraint objects.
template<typename... Args>
int readInt(int minValue, int maxValue, Args&&... constraints);
// Reads a signed 64-bit integer, checks that it's well-formed and lies in the given range.
long long readLong(long long minValue, long long maxValue);
// Reads an unsigned 64-bit integer, checks that it's well-formed and lies in the given range.
unsigned long long readULong(unsigned long long minValue, unsigned long long maxValue);
// Reads a floating point number, checks that it's well-formed, lies in the given range and
// has not more than a given number of digits after the decimal point.
double readDouble(double minValue, double maxValue, int maxDigits);
// Reads a floating point number, checks that it's well-formed, lies in the given range (">" or ">=" for min value,
// "<" or "<=" for max value) and has not more than a given number of digits after the decimal point.
double readDouble(const std::string& minRelation, double minValue, const std::string& maxRelation,
double maxValue, int maxDigits);
// Reads a series of signed 32-bit integers of a fixed length, where the numbers are separated with a single SPACE.
// Checks that each number lies in the given range. Checks each number with all provided constraint objects.
// Example: readIntVector(3, 1, 50) given the input "1 2 3" returns {1, 2, 3}.
template<typename... Args>
std::vector<int> readIntVector(int count, int minValue, int maxValue, Args&&... constraints);
// Reads a series of signed 32-bit integers of a fixed length, where the numbers are followed by a single EOLN.
// Checks that each number lies in the given range. Checks each number with all provided constraint objects.
// Example: readIntVectorLines(3, 1, 50) given the input "1\n2\n3\n" returns {1, 2, 3}.
template<typename... Args>
std::vector<int> readIntVectorLines(int count, int minValue, int maxValue, Args&&... constraints);
// Reads a series of signed 32-bit integers until the given end marker number, all separated with a single SPACE.
// Checks that each number lies in the given range. Checks each number with all provided constraint objects.
// Example: readIntVectorUntil(1, 50, -1) given the input "1 2 3 -1" returns {1, 2, 3}.
template<typename... Args>
std::vector<int> readIntVectorUntil(int minValue, int maxValue, int endMarker, Args&&... constraints);
// Reads a series of signed 32-bit integers until the given end marker number, all followed by a single EOLN.
// Checks that each number lies in the given range. Checks each number with all provided constraint objects.
// Example: readIntVectorUntilLines(1, 50, -1) given the input "1\n2\n3\n-1\n" returns {1, 2, 3}.
template<typename... Args>
std::vector<int> readIntVectorUntilLines(int minValue, int maxValue, int endMarker, Args&&... constraints);
// Reads a series of signed 32-bit integers of a fixed length, where the numbers are separated with a single SPACE.
// Checks that the numbers form a permutation with the given start number.
// Example: readPermutation(3) accepts "2 3 1", but rejects "1 2 2" and "0 1 2".
// Example: readPermutation(3, 0) accepts "1 2 0", but rejects "0 1 1" and "1 2 3".
std::vector<int> readPermutation(int count, int start = 1);
// Reads a series of signed 32-bit integers of a fixed length, where the numbers are followed by a single EOLN.
// Checks that the numbers form a permutation with the given start number.
// Example: readPermutationLines(3) accepts "2\n3\n1\n", but rejects "1\n2\n2\n" and "0\n1\n2\n".
// Example: readPermutationLines(3, 0) accepts "1\n2\n0\n", but rejects "0\n1\n1\n" and "1\n2\n3\n".
std::vector<int> readPermutationLines(int count, int start = 1);
// Check the condition and if it's not satisfied prints an error adding the current input position to it and
// finishes the program with the exit code 1. Should be called using the macro assert() defined below.
void _assert(bool condition, const char* expr) const;
// Prints a printf-style message adding the current input position to it. Finishes the program with the exit code 1.
void error(const char* fmt, ...) const;
};
// Check the condition and if it's not satisfied prints an error and finishes the program with the exit code 1.
// Should be called on an Input object, for example: Input in; int x = in.readInt(-10, 10); in.assert(x != 0);
#undef assert
#define assert(condition) _assert((condition), #condition)
// Prints a printf-style message. Finishes the program with the exit code 1.
void error(const char* fmt, ...);
// Returns whether the given graph is connected. Edges are given as pairs of 1-based node numbers.
// Example: isConnected(3, {{1, 2}, {2, 3}}) returns true. isConnected(4, {{1, 2}, {3, 4}}) returns false.
bool isConnected(int n, const std::vector<std::pair<int, int>>& edges);
// Check that the given graph is a tree. Edges are given as pairs of 1-based node numbers.
// Example: assertTree({{1, 2}, {1, 3}}) passes, while assertTree({{1, 3}}) and assertTree({{1, 2}, {1, 2}}) fail.
void assertTree(const std::vector<std::pair<int, int>>& tree);
// Check that the given graph is connected. Edges are given as pairs of 1-based node numbers.
// Example: assertConnected(3, {{1, 2}, {2, 3}}) passes, while assertConnected(4, {{1, 2}, {3, 4}}) fails.
void assertConnected(int n, const std::vector<std::pair<int, int>>& edges);
// Check that the given number is prime.
void assertPrime(int p);
// Returns the greatest common divisor of the given numbers.
long long gcd(long long a, long long b);
// Constraint checking the sum of the consumed numbers.
// Example: readIntVector(3, 1, 10, MaxSum(15)) accepts "2 3 10", but rejects "2 4 10".
class MaxSum
{
long long maxSum;
long long sum;
int pos;
public:
MaxSum(long long maxSum);
void operator()(long long value, const Input* in = nullptr);
};
// Checks that the sum of the numbers in the vector doesn't exceed the limit.
template<typename T>
void assertMaxSum(const std::vector<T>& values, long long maxSum);
// Constraint checking the monotonicity of the consumed values. Supports relations "<", "<=", ">", ">=".
// Example: readIntVector(3, 1, 10, Monotone<int>("<=")) accepts "1 3 3", but rejects "1 3 2".
template<typename T>
class Monotone
{
std::string rel;
std::optional<T> prev;
int pos;
public:
Monotone(const std::string& relation);
void operator()(const T& value, const Input* in = nullptr);
};
// Checks that the values in the vector are monotonic. Supports relations "<", "<=", ">", ">=".
template<typename T>
void assertMonotone(const std::vector<T>& values, const std::string& relation);
// Constraint checking that the consumed values are unique.
// Example: readIntVector(3, 1, 10, Unique<int>()) accepts "1 2 3", but rejects "1 2 2".
// Example: Unique<std::pair<int, int>> u; u({1, 2}); u({2, 1}); u({1, 2}); fails at the last call.
template<typename T>
class Unique
{
std::map<T, int> index;
public:
void operator()(const T& value, const Input* in = nullptr);
};
// Checks that the values in the vector are unique.
template<typename T>
void assertDistinct(const std::vector<T>& values);
// Constraint checking that the consumed numbers aren't equal to the given one.
// Example: readIntVector(3, 1, 10, NotEqual(5)) accepts "1 4 10", but rejects "1 5 10".
class NotEqual
{
long long notEqualValue;
public:
NotEqual(long long notEqualValue);
void operator()(long long value, const Input* in = nullptr);
};
// Constraint checking that the consumed numbers are odd.
// Example: readIntVector(3, 1, 9, Odd()) accepts "1 3 5", but rejects "1 3 4".
class Odd
{
public:
void operator()(long long value, const Input* in = nullptr);
};
// Constraint checking that the consumed numbers are even.
// Example: readIntVector(3, 2, 10, Even()) accepts "2 4 6", but rejects "2 4 5".
class Even
{
public:
void operator()(long long value, const Input* in = nullptr);
};
// ================================================== IMPLEMENTATION ==================================================
void Input::setBinaryMode()
{
#ifdef ON_WINDOWS
#ifdef STDIN_FILENO
int stdinFileno = STDIN_FILENO;
#else
int stdinFileno = _fileno(stdin);
#endif
if (_setmode(stdinFileno, O_BINARY) == -1)
::error("Cannot set stdin to binary mode");
#endif
}
void Input::nextChar()
{
if (isEoln())
{
line++;
pos = 1;
}
else
pos++;
c = getc(m_file);
#ifdef ON_WINDOWS
if (c == 10)
error("Unix style EOLN");
if (c == 13)
{
c = getc(m_file);
if (c != 10)
error("Character 13 without 10");
}
#else
if (c == 13)
error("Windows style EOLN");
#endif
}
void Input::assertDigit() const
{
if (c >= '0' && c <= '9')
return;
if (isEof())
error("EOF instead of number");
if (isEoln())
error("EOLN instead of number");
if (isSpace())
error("SPACE instead of number");
if (c == '\t')
error("TAB instead of number");
error("'%c' instead of number", (char)c);
}
void Input::init()
{
line = 1;
pos = 0;
c = 0;
nextChar();
}
void Input::parsePattern(const char* charPattern, bool valid[256]) const
{
for (int b = 0; b < 256; b++)
valid[b] = false;
for (int i = 0; charPattern[i]; i++)
{
unsigned char u = (unsigned char)charPattern[i];
if (u == '-' && i > 0 && charPattern[i + 1])
{
unsigned char from = (unsigned char)charPattern[i - 1];
unsigned char to = (unsigned char)charPattern[i + 1];
if (from > to)
error("wrong pattern: '%s'", charPattern);
for (int v = from; v <= to; v++)
valid[v] = true;
}
else
{
valid[u] = true;
}
}
}
template<typename T>
void Input::checkConstraints(const T&) const
{
}
template<typename T, typename First, typename... Args>
void Input::checkConstraints(const T& value, First&& first, Args&&... constraints) const
{
first(value, this);
checkConstraints(value, constraints...);
}
Input::Input()
{
setBinaryMode();
m_file = stdin;
init();
}
Input::Input(const char* fileName)
{
m_file = fopen(fileName, "rb");
if (!m_file)
::error("Cannot open file %s", fileName);
init();
}
Input::~Input()
{
fclose(m_file);
}
bool Input::isWhitespace() const
{
return c == ' ' || c == '\t' || c == '\n';
}
bool Input::isSpace() const
{
return c == ' ';
}
bool Input::isEoln() const
{
return c == '\n';
}
bool Input::isEof() const
{
return c == EOF;
}
bool Input::isChar(const char* charPattern) const
{
if (isEof())
return false;
bool valid[256];
parsePattern(charPattern, valid);
return valid[c];
}
void Input::readSpace()
{
if (!isSpace())
error("SPACE expected");
nextChar();
}
void Input::readZeroOrMoreSpaces()
{
while (isSpace())
nextChar();
}
void Input::readOneOrMoreSpaces()
{
readSpace();
readZeroOrMoreSpaces();
}
void Input::readEoln()
{
if (!isEoln())
error("EOLN expected");
nextChar();
}
void Input::readSpaceOrEoln()
{
if (!isSpace() && !isEoln())
error("EOLN or SPACE expected");
nextChar();
}
void Input::readEof()
{
if (!isEof())
error("EOF expected");
}
int Input::readChar()
{
if (isEof())
error("EOF instead of char");
int oldc = c;
nextChar();
return oldc;
}
int Input::readChar(const char* charPattern)
{
bool valid[256];
parsePattern(charPattern, valid);
if (isEof())
error("EOF instead of char");
if (!valid[c])
error("character '%c' does not match pattern '%s'", (char)c, charPattern);
int oldc = c;
nextChar();
return oldc;
}
std::string Input::readToken()
{
if (isEof())
error("EOF instead of token");
if (isWhitespace())
error("whitespace instead of token");
std::string res;
while (!isWhitespace() && !isEof())
{
res += (char)c;
nextChar();
}
return res;
}
template<typename... Args>
std::string Input::readToken(int minLength, int maxLength, const char* charPattern, Args&&... constraints)
{
bool valid[256];
parsePattern(charPattern, valid);
if (isEof())
error("EOF instead of token");
if (isWhitespace())
error("whitespace instead of token");
std::string res;
while (!isWhitespace() && !isEof())
{
res += (char)c;
if ((int)res.length() > maxLength)
error("the length of token exceeded %d", maxLength);
if (!valid[c])
error("character '%c' does not match pattern '%s'", (char)c, charPattern);
nextChar();
}
if ((int)res.length() < minLength)
error("the length of token is less than %d", minLength);
checkConstraints(res, std::forward<Args>(constraints)...);
return res;
}
template<typename... Args>
std::string Input::readToken(const std::string& regexp, Args&&... constraints)
{
std::string token = readToken();
if (!std::regex_match(token, std::regex(regexp)))
error("token does not match regexp %s", regexp.c_str());
checkConstraints(token, std::forward<Args>(constraints)...);
return token;
}
std::string Input::readLine()
{
std::string res;
while (!isEoln())
{
if (isEof())
error("EOF instead of EOLN");
res += (char)c;
nextChar();
}
nextChar();
return res;
}
std::string Input::readLine(int minLength, int maxLength, const char* charPattern)
{
bool valid[256];
parsePattern(charPattern, valid);
std::string res;
while (!isEoln())
{
if (isEof())
error("EOF instead of EOLN");
res += (char)c;
if ((int)res.length() > maxLength)
error("the length of line exceeded %d", maxLength);
if (!valid[c])
error("character '%c' does not match pattern '%s'", (char)c, charPattern);
nextChar();
}
if ((int)res.length() < minLength)
error("the length of line is less than %d", minLength);
nextChar();
return res;
}
std::string Input::readLine(const std::string& regexp)
{
std::string res;
while (!isEoln())
{
if (isEof())
error("EOF instead of EOLN");
res += (char)c;
nextChar();
}
if (!std::regex_match(res, std::regex(regexp)))
error("line does not match regexp %s", regexp.c_str());
nextChar();
return res;
}
template<typename... Args>
int Input::readInt(int minValue, int maxValue, Args&&... constraints)
{
int value = (int)readLong(minValue, maxValue);
checkConstraints(value, std::forward<Args>(constraints)...);
return value;
}
long long Input::readLong(long long minValue, long long maxValue)
{
bool minus = false;
long long x = 0;
if (c == '-')
{
minus = true;
nextChar();
}
assertDigit();
if (c == '0')
{
nextChar();
if (c >= '0' && c <= '9')
error("integer with leading zero");
else if (minus)
error("minus zero");
}
else
{
const long long MIN_LONG = 0x8000000000000000ll;
const long long MIN_LONG_DIV10 = MIN_LONG / 10;
const long long MIN_LONG_MOD10 = -(MIN_LONG % 10);
const long long MAX_LONG = 0x7fffffffffffffffll;
const long long MAX_LONG_DIV10 = MAX_LONG / 10;
const long long MAX_LONG_MOD10 = MAX_LONG % 10;
while (c >= '0' && c <= '9')
{
long long digit = c - '0';
if (minus)
{
if (x < MIN_LONG_DIV10 || (x == MIN_LONG_DIV10 && digit > MIN_LONG_MOD10))
error("overflow of 64-bit signed integer");
x = x * 10 - digit;
}
else
{
if (x > MAX_LONG_DIV10 || (x == MAX_LONG_DIV10 && digit > MAX_LONG_MOD10))
error("overflow of 64-bit signed integer");
x = x * 10 + digit;
}
nextChar();
}
}
if (x < minValue || x > maxValue)
error("integer %lld is out of bounds [%lld, %lld]", x, minValue, maxValue);
return x;
}
unsigned long long Input::readULong(unsigned long long minValue, unsigned long long maxValue)
{
unsigned long long x = 0;
assertDigit();
if (c == '0')
{
nextChar();
if (c >= '0' && c <= '9')
error("integer with leading zero");
}
else
{
const unsigned long long MAX_ULONG = 0xffffffffffffffffull;
const unsigned long long MAX_ULONG_DIV10 = MAX_ULONG / 10ull;
const unsigned long long MAX_ULONG_MOD10 = MAX_ULONG % 10ull;
while (c >= '0' && c <= '9')
{
unsigned long long digit = c - '0';
if (x > MAX_ULONG_DIV10 || (x == MAX_ULONG_DIV10 && digit > MAX_ULONG_MOD10))
error("overflow of 64-bit unsigned integer");
x = x * 10u + digit;
nextChar();
}
}
if (x < minValue || x > maxValue)
error("integer %llu is out of bounds [%llu, %llu]", x, minValue, maxValue);
return x;
}
double Input::readDouble(const std::string& minRelation, double minValue, const std::string& maxRelation,
double maxValue, int maxDigits)
{
if (!(minRelation == ">" || minRelation == ">="))
error("Unsupported minRelation: '%s'", minRelation.c_str());
if (!(maxRelation == "<" || maxRelation == "<="))
error("Unsupported maxRelation: '%s'", maxRelation.c_str());
if (maxDigits < 1 || maxDigits > 15)
error("Unsupported maxDigits: %d", maxDigits);
bool minus = false;
bool wasDigit = false;
double x = 0.0;
if (c == '-')
{
minus = true;
nextChar();
}
if (c == '0')
{
nextChar();
if (c >= '0' && c <= '9')
error("double with leading zero");
wasDigit = true;
}
while (c >= '0' && c <= '9')
{
x = x * 10.0 + (c - '0');
nextChar();
wasDigit = true;
}
if (c == '.')
{
if (!wasDigit)
error("double starts with dot");
nextChar();
if (c < '0' || c > '9')
error("double ends with dot");
double y = 0.1;
for (int k = 1; c >= '0' && c <= '9'; k++)
{
if (k > maxDigits)
error("more than %d digits after decimal point", maxDigits);
x += y * (double)(c - '0');
y *= 0.1;
nextChar();
wasDigit = true;
}
}
if (!wasDigit)
assertDigit();
if (minus && x == 0.0)
error("minus zero");
if (minus)
x = -x;
double eps = std::pow(10.0, -(maxDigits + 1));
if (!(((minRelation == ">" && x > minValue + eps) || (minRelation == ">=" && x >= minValue - eps)) &&
((maxRelation == "<" && x < maxValue - eps) || (maxRelation == "<=" && x <= maxValue + eps))))
error("number %g is out of bounds %c%g, %g%c", x, minRelation == ">" ? '(' : '[', minValue, maxValue,
maxRelation == "<" ? ')' : ']');
return x;
}
double Input::readDouble(double minValue, double maxValue, int maxDigits)
{
return readDouble(">=", minValue, "<=", maxValue, maxDigits);
}
template<typename... Args>
std::vector<int> Input::readIntVector(int count, int minValue, int maxValue, Args&&... constraints)
{
std::vector<int> result;
for (int i = 0; i < count; i++)
{
if (i > 0)
readSpace();
result.push_back(readInt(minValue, maxValue, std::forward<Args>(constraints)...));
}
return result;
}
template<typename... Args>
std::vector<int> Input::readIntVectorLines(int count, int minValue, int maxValue, Args&&... constraints)
{
std::vector<int> result;
for (int i = 0; i < count; i++)
{
result.push_back(readInt(minValue, maxValue, std::forward<Args>(constraints)...));
readEoln();
}
return result;
}
template<typename... Args>
std::vector<int> Input::readIntVectorUntil(int minValue, int maxValue, int endMarker, Args&&... constraints)
{
std::vector<int> result;
while (true)
{
int value = readInt(-2147483648, 2147483647);
if (value == endMarker)
break;
if (!(value >= minValue && value <= maxValue))
error("integer %d is out of bounds [%d, %d]", value, minValue, maxValue);
checkConstraints(value, std::forward<Args>(constraints)...);
result.push_back(value);
readSpace();
}
return result;
}
template<typename... Args>
std::vector<int> Input::readIntVectorUntilLines(int minValue, int maxValue, int endMarker, Args&&... constraints)
{
std::vector<int> result;
while (true)
{
int value = readInt(-2147483648, 2147483647);
if (value == endMarker)
break;
if (!(value >= minValue && value <= maxValue))
error("integer %d is out of bounds [%d, %d]", value, minValue, maxValue);
checkConstraints(value, std::forward<Args>(constraints)...);
result.push_back(value);
readEoln();
}
readEoln();
return result;
}
std::vector<int> Input::readPermutation(int count, int start)
{
return readIntVector(count, start, start + count - 1, Unique<int>());
}
std::vector<int> Input::readPermutationLines(int count, int start)
{
return readIntVectorLines(count, start, start + count - 1, Unique<int>());
}
void Input::_assert(bool condition, const char* expr) const
{
if (!condition)
error("condition failed: %s ", expr);
}
void Input::error(const char* fmt, ...) const
{
va_list argptr;
va_start(argptr, fmt);
fprintf(stderr, "Line %d, pos %d: ", line, pos);
vfprintf(stderr, fmt, argptr);
fprintf(stderr, " ");
va_end(argptr);
exit(1);
}
void error(const char* fmt, ...)
{
va_list argptr;
va_start(argptr, fmt);
vfprintf(stderr, fmt, argptr);
fprintf(stderr, " ");
va_end(argptr);
exit(1);
}
bool isConnected(int n, const std::vector<std::pair<int, int>>& edges)
{
std::vector<bool> used(n, false);
std::vector<std::vector<int>> adj(n);
std::queue<int> q;
for (unsigned int i = 0; i < edges.size(); i++)
{
if (edges[i].first < 1 || edges[i].first > n)
error("Incorrect vertex number: %d", edges[i].first);
if (edges[i].second < 1 || edges[i].second > n)
error("Incorrect vertex number: %d", edges[i].second);
adj[edges[i].first - 1].push_back(edges[i].second - 1);
adj[edges[i].second - 1].push_back(edges[i].first - 1);
}
used[0] = true;
q.push(0);
while (!q.empty())
{
int x = q.front();
q.pop();
for (unsigned int j = 0; j < adj[x].size(); j++)
{
int y = adj[x][j];
if (!used[y])
{
used[y] = true;
q.push(y);
}
}
}
for (int u = 0; u < n; u++)
if (!used[u])
return false;
return true;
}
void assertTree(const std::vector<std::pair<int, int>>& tree)
{
if (!isConnected((int)tree.size() + 1, tree))
error("Graph is not a tree");
}
void assertConnected(int n, const std::vector<std::pair<int, int>>& edges)
{
if (!isConnected(n, edges))
error("Graph is not connected");
}
void assertPrime(int p)
{
if (p <= 0)
error("Non-positive number: %d", p);
int i;
for (i = 2; i * i <= p; i++)
if (p % i == 0) break;
if (p < 2 || i * i <= p)
error("Number is not a prime: %d", p);
}
long long gcd(long long a, long long b)
{
a = a < 0 ? -a : a;
b = b < 0 ? -b : b;
while (b > 0) {
long long c = a % b;
a = b;
b = c;
}
return a;
}
#define InputOrFreeError(in, ...) \
do { if ((in) != nullptr) (in)->error(__VA_ARGS__); else error(__VA_ARGS__); } while (false)
MaxSum::MaxSum(long long maxSum)
: maxSum(maxSum), sum(0), pos(0)
{
}
void MaxSum::operator()(long long value, const Input* in)
{
pos++;
if (value < 0)
InputOrFreeError(in, "negative number at position %d", pos);
sum += value;
if (sum > maxSum)
InputOrFreeError(in, "sum exceeded %lld at position %d", maxSum, pos);
}
template<typename T>
void assertMaxSum(const std::vector<T>& values, long long maxSum)
{
MaxSum sum(maxSum);
for (const T& value : values)
sum(value);
}
template<typename T>
Monotone<T>::Monotone(const std::string& relation)
: rel(relation), pos(0)
{
if (!(rel == "<" || rel == "<=" || rel == ">" || rel == ">="))
error("Unsupported relation: '%s'", rel.c_str());
}
template<typename T>
void Monotone<T>::operator()(const T& value, const Input* in)
{
pos++;
if (prev.has_value())
{
const T& x = *prev;
const T& y = value;
if (!(rel == "<" && x < y || rel == "<=" && x <= y || rel == ">" && x > y || rel == ">=" && x >= y))
InputOrFreeError(in, "expected relation %s at positions %d and %d", rel.c_str(), pos - 1, pos);
}
prev = value;
}
template<typename T>
void assertMonotone(const std::vector<T>& values, const std::string& relation)
{
Monotone<T> monotone(relation);
for (const T& value : values)
monotone(value);
}
template<typename T>
void Unique<T>::operator()(const T& value, const Input* in)
{
int position = static_cast<int>(index.size()) + 1;
auto [it, inserted] = index.insert({value, position});
if (!inserted)
InputOrFreeError(in, "duplicate elements at positions %d and %d", it->second, position);
}
template<typename T>
void assertDistinct(const std::vector<T>& values)
{
Unique<T> unique;
for (const T& value : values)
unique(value);
}
NotEqual::NotEqual(long long notEqualValue)
: notEqualValue(notEqualValue)
{
}
void NotEqual::operator()(long long value, const Input* in)
{
if (value == notEqualValue)
InputOrFreeError(in, "unexpected integer %lld", value);
}
void Odd::operator()(long long value, const Input* in)
{
if (value % 2 == 0)
InputOrFreeError(in, "integer %lld is not odd", value);
}
void Even::operator()(long long value, const Input* in)
{
if (value % 2 != 0)
InputOrFreeError(in, "integer %lld is not even", value);
}