QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#699170 | #7696. Forest for the Trees | snowythecat | AC ✓ | 440ms | 842304kb | C++20 | 14.9kb | 2024-11-02 02:48:45 | 2024-11-02 02:48:45 |
Judging History
answer
//must be compiled with c++20
/*
#pragma GCC target ("avx2")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
*/
#pragma GCC optimize ("unroll-loops")
#include <algorithm>
#include <bits/stdc++.h>
#include <cerrno>
#include <ext/pb_ds/assoc_container.hpp>
#include <type_traits>
using namespace __gnu_pbds;
using namespace std;
#define fasterthanlight cin.tie(0); ios::sync_with_stdio(0);
#define ll long long
#define lll __int128
const ll inf = 1e9 + 7;
const ll inf2 = 1e9 + 9;
const ll inff= 998244353;
const ll infh = (1LL << 61) - 1;
#define pll pair<ll,ll>
#define pii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define f0(i,n) for (int i=0;i<n;i++)
#define f1(i,n) for (int i=1;i<=n;i++)
#define ff0(i,n) for (int i=n-1;i>-1;i--)
#define ff1(i,n) for (int i=n;i>0;i--)
#define fs(i,a,b) for (int i=a;i<b;i++)
#define testcases int tzxhicjkha; cin>>tzxhicjkha;while (tzxhicjkha--)
#define usingfloats cout<<setprecision(20)
#define ineedtohash mll iqknabxiopk=1;for (ll iqknabxiop=0;iqknabxiop<HASHPOWMAX;iqknabxiop++){pows[iqknabxiop]=iqknabxiopk;iqknabxiopk*=B;}
#define sz(x) ((int)(x.size()))
template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}
//2*10^6 powers for hashing
const ll HASHPOWMAX=7000005;
int msb(int n)
{
if (n==0){
//cout<<"F";
return 0;
}
int k = __builtin_clz(n);
return 31 - k;
}
ll lmsb(ll n)
{
if (n==0){
//cout<<"F";
return 0;
}
int k = __builtin_clzll(n);
return 63 - k;
}
//I have no idea if the below code is safe or good
istream &operator>>(istream &is,__int128 &v) {
string s;
is>>s;
v=0;
for(auto &it:s) if(isdigit(it)) v=v*10+it-'0';
if(s[0]=='-') v*=-1;
return is;
}
ostream &operator<<(ostream &os,const __int128 &v) {
if(v==0) return (os<<"0");
__int128 num=v;
if(v<0) os<<'-',num=-num;
string s;
for(;num>0;num/=10) s.pb((char)(num%10)+'0');
reverse(all(s));
return (os<<s);
}
template<typename T, typename Q> istream &operator>>(istream &is, pair<T,Q> &v) {
is>>v.first>>v.second;
return is;
}
template<typename T, typename Q>ostream &operator<<(ostream &os,const pair<T,Q> &v) {
return (os<<v.first<<" "<<v.second);
}
//some cursed cin vector shit
template<typename T> istream &operator>>(istream &is,vector<T> &v) {
for (T&i:v){
is>>i;
}
return is;
}
template<typename T> ostream &operator<<(ostream &os,const vector<T> &v) {
if (v.empty()){
return os;
}
for (int i=0;i<v.size()-1;i++){
os<<v[i]<<" ";
}
return os<<v[v.size()-1];
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
//const ll B = 100;
const ll B = uniform_int_distribution<ll>(1000, inf - 1)(rng);
/*
//some cursed code
//allows int x=in;
struct {
template<class T>
operator T() {
T x; std::cin >> x; return x;
}
} in;
//breaks if string
//so do string s = (string)in;
*/
//ty Mark for modint code that I will change
template<long long MOD>
struct ModInt {
long long v;
ModInt() {
v=0;
}
ModInt(long long _v) {
v = _v % MOD;
if (v < 0) {
v += MOD;
}
}
friend ModInt pow(ModInt base, long long exp) {
ModInt res = 1;
while (exp) {
if (exp & 1) {
res *= base;
}
base *= base;
exp >>= 1;
}
return res;
}
ModInt &operator+=(ModInt b) {
if ((v += b.v) >= MOD) {
v -= MOD;
}
return *this;
}
ModInt &operator-=(ModInt b) {
if ((v -= b.v) < 0) {
v += MOD;
}
return *this;
}
ModInt &operator*=(ModInt b) {
if constexpr (MOD==infh){
//UNSAFE CODE PROBABLY
uint64_t l1 = uint32_t(v), h1 = v >> 32;
uint64_t l2 = uint32_t(b.v), h2 = b.v >> 32;
uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
uint64_t ret = (l & MOD) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
ret = (ret & MOD) + (ret >> 61);
ret = (ret & MOD) + (ret >> 61);
v = ret - 1;
return *this;
}
else if constexpr (MOD<=INT_MAX){
//if less than or equal to INT_MAX, lll isn't needed
v=v * b.v % MOD;
return *this;
}
else{
v = (__int128)1 * v * b.v % MOD;
return *this;
}
}
//division is scuffed
ModInt &operator/=(ModInt b) {
*this *= pow(b, MOD - 2);
return *this;
}
friend ModInt operator+(ModInt a, ModInt b) {
return a += b;
}
friend ModInt operator-(ModInt a, ModInt b) {
return a -= b;
}
friend ModInt operator*(ModInt a, ModInt b) {
return a *= b;
}
friend ModInt operator/(ModInt a, ModInt b) {
return a /= b;
}
friend istream &operator>>(istream &is, ModInt &a) {
long long x;
is >> x;
a = ModInt(x);
return is;
}
friend ostream &operator<<(ostream &os, ModInt a) {
return os << a.v;
}
bool operator==(const ModInt& y) const{
return v == y.v;
}
bool operator!=(const ModInt& y) const{
return v != y.v;
}
ModInt& operator++() {
v++;
if (v == MOD) v = 0;
return *this;
}
ModInt& operator--() {
if (v == 0) v = MOD;
v--;
return *this;
}
ModInt operator++(int) {
ModInt result = *this;
++*this;
return result;
}
ModInt operator--(int) {
ModInt result = *this;
--*this;
return result;
}
//bad operators for completeness sake
bool operator>(const ModInt& y) const{
return v > y.v;
}
bool operator>=(const ModInt& y) const{
return v >= y.v;
}
bool operator<=(const ModInt& y) const{
return v <= y.v;
}
bool operator<(const ModInt& y) const{
return v < y.v;
}
};
using mll = ModInt<infh>;
using mint = ModInt<inf>;
using minf = ModInt<inff>;
ll exp(ll x, ll n, ll m=inf) {
assert(n >= 0);
x %= m; // note: m * m must be less than 2^63 to avoid ll overflow
ll res = 1;
while (n > 0) {
if (n % 2 == 1) { res = res * x % m; }
x = x * x % m;
n /= 2;
}
return res;
}
ll expu(ll x, ll n) {
assert(n >= 0);
ll res = 1;
while (n > 0) {
if (n % 2 == 1) { res = res * x; }
x = x * x;
n /= 2;
}
return res;
}
mll exph(mll base, ll exp) {
mll res = 1;
while (exp) {
if (exp & 1) {
res *= base;
}
base *= base;
exp >>= 1;
}
return res;
}
minf expf(minf base, ll exp) {
minf res = 1;
while (exp) {
if (exp & 1) {
res *= base;
}
base *= base;
exp >>= 1;
}
return res;
}
mint expo(mint base, ll exp) {
mint res = 1;
while (exp) {
if (exp & 1) {
res *= base;
}
base *= base;
exp >>= 1;
}
return res;
}
vector<mll> pows(HASHPOWMAX);
const mll HMODINV=exph(B,infh-2);
struct hashPart {
mll value;
int len;
hashPart() {
value=0;
len=0;
}
hashPart(mll x, int y) : value(x), len(y) {}
hashPart operator+=(hashPart b) {
hashPart a=hashPart(value * pows[b.len] + b.value, len + b.len);
(*this).value=a.value;
(*this).len=a.len;
return *this;
}
hashPart operator+(hashPart b) {
return hashPart(value * pows[b.len] + b.value, len + b.len);
}
hashPart operator-(hashPart b) {
return hashPart(value + b.value, len);
}
bool operator==(hashPart b) {
return value == b.value;
}
};
template<class T>
struct hashString {
vector<mll> hash;
hashString(T s) {
hash.resize(int(s.size()) + 1);
for (int i = 0; i < int(s.size()); i++) {
hash[i + 1] = (hash[i] * B + s[i]);
}
while (int(pows.size()) < int(hash.size())) {
pows.push_back(pows.back() * B);
}
}
hashPart getHash(int l, int r) {
return hashPart(hash[r] -hash[l] * pows[r - l], r - l);
}
hashPart getHash() {
return getHash(0, hash.size() - 1);
}
};
//I don't understand the below code, all I know is it's good for hashing apparently
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
ll es(ll x1, ll y1, ll x2, ll y2){
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
ll man(ll x1, ll y1, ll x2, ll y2){
return abs(x1-x2)+abs(y1-y2);
}
minf choose(int n,int k){
if (k>n){
return 0;
}
minf ret=1;
for (int i=n;i>n-k;i--){
ret*=i;
}
for (int i=1;i<=k;i++){
ret/=i;
}
return ret;
}
//stolen from geeks for geeks
vector<int> sieve(int n)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
bool prime[n + 1];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it numbers which are
// multiple of p and are less than p^2 are
// already been marked.
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
vector<int> ret;
// Print all prime numbers
for (int p = 2; p <= n; p++)
if (prime[p])
ret.pb(p);
return ret;
}
void setup(){
}
typedef tree<double,null_type,less_equal<double>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
void solve(){
ll rmax;
ll tottree;
ll sentree;
cin>>tottree>>sentree>>rmax;
vector<pair<ll,ll>> altre;
map<pair<int,int>,bool> treethere;
for (ll i=0;i<tottree;i++){
ll a,b;
cin>>a>>b;
altre.pb({a,b});
treethere[{a,b}]=1;
}
vector<pair<ll,ll>> goodpolls;
ll q=0;
for (ll i=-rmax;i<=rmax;i++){
ll rem=rmax-abs(i);
for (ll j=-rem;j<=rem;j++){
//cout<<i<<" "<<j<<" "<<q<<"\n";
q++;
}
}
//map<pair<ll,ll>,ll> offset;
vector<ll> offset(10000*10000);
for (ll i=-rmax;i<=rmax;i++){
ll rem=rmax-abs(i);
for (ll j=-rem;j<=rem;j++){
//cout<<i<<" "<<j<<" "<<q<<"\n";
offset[(4000+i)*7000+(4000+j)]=q;
//offset[{i,j}]=q;
q--;
}
}
ll a,b;
mll ans1=0;
for (ll i=0;i<sentree;i++){
cin>>a>>b;
/*if (a==0&&b==0){
cout<<"Impossible\n";
return;
}*/
ans1+=pows[offset[(4000+a)*7000+(4000+b)]-1];
}
//cout<<ans1<<"\n";
//subtract one from offset later
vector<pair<ll,ll>> pois;
map<pair<int,int>,bool> claimed;
for (auto i:altre){
ll x=-a;
ll y=-b;
if ((!claimed[{i.first+x,i.second+y}])&&(!treethere[{i.first+x,i.second+y}])){
claimed[{i.first+x,i.second+y}]=1;
pois.pb({i.first+x,i.second+y});
}
if ((!claimed[{i.first-y,i.second+x}])&&(!treethere[{i.first-y,i.second+x}])){
claimed[{i.first-y,i.second+x}]=1;
pois.pb({i.first-y,i.second+x});
}
if ((!claimed[{i.first-x,i.second-y}])&&(!treethere[{i.first-x,i.second-y}])){
claimed[{i.first-x,i.second-y}]=1;
pois.pb({i.first-x,i.second-y});
}
if ((!claimed[{i.first+y,i.second-x}])&&(!treethere[{i.first+y,i.second-x}])){
claimed[{i.first+y,i.second-x}]=1;
pois.pb({i.first+y,i.second-x});
}
}
for (auto i:pois){
pair<ll,ll> poi;
mll ans;
//x,y
poi=i;
ans=0;
for (auto j:altre){
ll x=j.first-poi.first;
ll y=j.second-poi.second;
if ((abs(x)+abs(y)<=rmax)){
ll exp=offset[(4000+x)*7000+(4000+y)]-1;
ans+=pows[exp];
}
}
//cout<<poi<<" "<<ans<<"\n";
if (ans==ans1){
goodpolls.pb(poi);
}
//-y,x
poi=i;
ans=0;
for (auto j:altre){
ll x=j.first-poi.first;
ll y=j.second-poi.second;
if ((abs(x)+abs(y)<=rmax)){
ll exp=offset[(4000-y)*7000+(4000+x)]-1;
ans+=pows[exp];
}
}
//cout<<poi<<" "<<ans<<"\n";
if (ans==ans1){
goodpolls.pb(poi);
}
//-x,-y
poi=i;
ans=0;
for (auto j:altre){
ll x=j.first-poi.first;
ll y=j.second-poi.second;
if ((abs(x)+abs(y)<=rmax)){
ll exp=offset[(4000-x)*7000+(4000-y)]-1;
ans+=pows[exp];
}
}
//cout<<poi<<" "<<ans<<"\n";
if (ans==ans1){
goodpolls.pb(poi);
}
//y,-x
poi=i;
ans=0;
for (auto j:altre){
ll x=j.first-poi.first;
ll y=j.second-poi.second;\
if ((abs(x)+abs(y)<=rmax)){
//cout<<y<<" "<<-x<<"\n";
ll exp=offset[(4000+y)*7000+(4000-x)]-1;
ans+=pows[exp];
}
}
//cout<<poi<<" "<<ans<<"\n";
if (ans==ans1){
goodpolls.pb(poi);
}
}
if (goodpolls.size()==0){
cout<<"Impossible\n";
return;
}
if (goodpolls.size()>1){
cout<<"Ambiguous\n";
return;
}
cout<<goodpolls<<"\n";
}
signed main() {
setup();
//usingfloats;
fasterthanlight;
ineedtohash;
//testcases{
solve();
//}
}
详细
Test #1:
score: 100
Accepted
time: 64ms
memory: 839072kb
input:
4 4 100 1 1 2 2 2 1 3 3 0 1 0 2 -1 2 -2 3
output:
0 1
result:
ok single line: '0 1'
Test #2:
score: 0
Accepted
time: 55ms
memory: 839216kb
input:
4 4 4 0 1 1 0 0 -1 -1 0 0 1 1 0 0 -1 -1 0
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #3:
score: 0
Accepted
time: 283ms
memory: 841016kb
input:
4899 957 32 -9961 -9999 -9970 -9968 -9942 -9986 -9991 -9991 -9950 -9990 -9958 -9994 -9939 -9944 -9992 -9987 -9973 -9937 -9981 -9941 -9940 -9940 -9989 -9945 -9961 -9963 -9970 -9932 -9969 -9967 -9977 -9971 -9949 -9989 -9958 -9958 -9957 -9993 -9937 -9935 -9938 -9980 -9965 -9997 -9992 -9951 -9946 -9984 ...
output:
-9929 -9959
result:
ok single line: '-9929 -9959'
Test #4:
score: 0
Accepted
time: 404ms
memory: 841176kb
input:
4899 941 40 -9970 -9968 -9942 -9986 -9991 -9991 -9950 -9990 -9958 -9994 -9939 -9944 -9992 -9987 -9973 -9937 -9981 -9941 -9940 -9940 -9989 -9945 -9961 -9963 -9970 -9932 -9969 -9967 -9977 -9971 -9949 -9989 -9958 -9958 -9957 -9993 -9937 -9935 -9938 -9980 -9965 -9997 -9992 -9951 -9946 -9984 -10000 -9955...
output:
Impossible
result:
ok single line: 'Impossible'
Test #5:
score: 0
Accepted
time: 396ms
memory: 841132kb
input:
4899 940 40 -9970 -9968 -9942 -9986 -9991 -9991 -9950 -9990 -9958 -9994 -9939 -9944 -9992 -9987 -9973 -9937 -9981 -9941 -9940 -9940 -9989 -9945 -9961 -9963 -9970 -9932 -9969 -9967 -9977 -9971 -9949 -9989 -9958 -9958 -9957 -9993 -9937 -9935 -9938 -9980 -9965 -9997 -9992 -9951 -9946 -9984 -10000 -9955...
output:
Impossible
result:
ok single line: 'Impossible'
Test #6:
score: 0
Accepted
time: 71ms
memory: 839104kb
input:
3 3 1000 1 0 0 1 1 1 1 0 0 1 1 1
output:
0 0
result:
ok single line: '0 0'
Test #7:
score: 0
Accepted
time: 440ms
memory: 842304kb
input:
5000 2 1000 0 0 1000 1000 66740 84615 -16851 37613 31009 31589 -68041 -71122 21568 86889 53743 -31217 -73472 63365 9594 -12742 -25497 -5264 15942 13442 19537 -83361 93129 67319 -27565 73861 75273 -19266 -55048 -79726 -45975 -36987 -51309 35820 -99049 -10933 -45867 99815 -52121 99729 -89976 -15892 38...
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #8:
score: 0
Accepted
time: 436ms
memory: 842232kb
input:
5000 3 1000 0 0 1000 1000 1000 999 13954 9751 75888 -54632 10747 -12901 37707 -37988 -49564 26056 -30528 -9620 6227 -95560 -82768 85135 -15530 89254 -39739 -79664 -81590 -75580 91135 -20238 -52264 -66253 -41259 -90627 -7096 -35158 -67316 13384 79722 57595 -40566 99205 35854 -48598 -83531 -59472 -286...
output:
600 400
result:
ok single line: '600 400'
Test #9:
score: 0
Accepted
time: 59ms
memory: 839236kb
input:
4 3 100 1 1 2 2 2 1 3 3 0 1 0 2 -1 2
output:
Impossible
result:
ok single line: 'Impossible'
Test #10:
score: 0
Accepted
time: 68ms
memory: 839164kb
input:
3 3 100 1 1 2 1 3 1 0 1 0 2 0 3
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #11:
score: 0
Accepted
time: 60ms
memory: 839216kb
input:
4 3 2 1 1 2 2 2 1 3 3 0 1 0 2 -1 1
output:
2 0
result:
ok single line: '2 0'
Test #12:
score: 0
Accepted
time: 55ms
memory: 839272kb
input:
121 121 50 4 0 -10 10 8 0 0 -4 -6 10 -8 -8 10 6 2 2 -8 10 -4 -8 6 2 -2 -2 -10 -6 -4 10 4 2 -6 -6 10 -10 8 2 0 -2 -8 -6 2 4 -4 -6 6 4 -2 0 -10 -4 -6 -4 10 -8 8 4 0 0 -8 -4 -4 -4 6 6 -2 2 -10 -2 -6 -2 10 -6 2 -10 0 2 -8 -2 6 -10 -4 -2 4 -10 -2 4 -10 0 8 -10 -6 0 2 -8 -8 0 6 -8 10 8 -4 0 -10 2 8 -8 -6 ...
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #13:
score: 0
Accepted
time: 51ms
memory: 839264kb
input:
120 120 50 -10 10 8 0 0 -4 -6 10 -8 -8 10 6 2 2 -8 10 -4 -8 6 2 -2 -2 -10 -6 -4 10 4 2 -6 -6 10 -10 8 2 0 -2 -8 -6 2 4 -4 -6 6 4 -2 0 -10 -4 -6 -4 10 -8 8 4 0 0 -8 -4 -4 -4 6 6 -2 2 -10 -2 -6 -2 10 -6 2 -10 0 2 -8 -2 6 -10 -4 -2 4 -10 -2 4 -10 0 8 -10 -6 0 2 -8 -8 0 6 -8 10 8 -4 0 -10 2 8 -8 -6 2 4 ...
output:
5 5
result:
ok single line: '5 5'
Test #14:
score: 0
Accepted
time: 91ms
memory: 839152kb
input:
120 119 50 -10 10 8 0 0 -4 -6 10 -8 -8 10 6 2 2 -8 10 -4 -8 6 2 -2 -2 -10 -6 -4 10 4 2 -6 -6 10 -10 8 2 0 -2 -8 -6 2 4 -4 -6 6 4 -2 0 -10 -4 -6 -4 10 -8 8 4 0 0 -8 -4 -4 -4 6 6 -2 2 -10 -2 -6 -2 10 -6 2 -10 0 2 -8 -2 6 -10 -4 -2 4 -10 -2 4 -10 0 8 -10 -6 0 2 -8 -8 0 6 -8 10 8 -4 0 -10 2 8 -8 -6 2 4 ...
output:
Impossible
result:
ok single line: 'Impossible'
Test #15:
score: 0
Accepted
time: 64ms
memory: 839148kb
input:
121 121 50 4 0 -10 10 8 0 0 -4 -6 10 -8 -8 10 6 2 2 -8 10 -4 -8 6 2 -2 -2 -10 -6 -4 10 4 2 -6 -6 10 -10 8 2 0 -2 -8 -6 2 4 -4 -6 6 4 -2 0 -10 -4 -6 -4 10 -8 8 4 0 0 -8 -4 -4 -4 6 6 -2 2 -10 -2 -6 -2 10 -6 2 -10 0 2 -8 -2 6 -10 -4 -2 4 -10 -2 4 -10 0 8 -10 -6 0 2 -8 -8 0 6 -8 10 8 -4 0 -10 2 8 -8 -6 ...
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #16:
score: 0
Accepted
time: 151ms
memory: 839760kb
input:
2598 217 20 -28 50 -36 46 -16 24 -24 20 50 6 -44 -38 42 2 6 48 -42 8 -50 4 -30 -18 -38 -22 -20 26 -18 -44 -38 14 2 50 -46 10 -18 -8 22 28 -26 -12 14 24 -34 -16 -6 -34 -14 -38 26 -2 -22 -42 18 -6 -4 12 36 48 -12 8 8 -14 48 22 0 -18 18 30 -8 -22 20 -40 12 -44 30 4 4 -48 -8 14 12 -8 4 -12 44 24 24 -34 ...
output:
5 5
result:
ok single line: '5 5'