oj.uz

Submission #1081604

# Submission time Handle Problem Language Result Execution time Memory
1081604 2024-08-30T08:02:28 Z dong_gas Magic Show (APIO24_show) C++17
0 / 100
 3 ms 1268 KB 
#include <bits/extc++.h>
#include "Alice.h"
#include "Bob.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
using namespace __gnu_pbds;
template<class T> using PBDS = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using multiPBDS = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector<pint> Alice(){
    ll x = setN(5000);
    vector<pint> edges;
    for(int i=2;i<=5000;i++) edges.push_back({x%(i-1)+1,i});
    return edges;
}
#include <bits/extc++.h>
#include "Alice.h"
#include "Bob.h"
#define all(v) v.begin(), v.end()
#define zip(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
using namespace __gnu_pbds;
template<class T> using PBDS = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using multiPBDS = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll gcd(ll a, ll b)
{
	if(a==0) return b;
	if(b==0) return a;
	return gcd(b, a%b);
}

ll minv(ll a, ll b)
{
	if(a==0 && b==1) return 0;
	if(a==1) return 1;
	return b - minv(b%a, a) * b / a;
}

// x == A.first (mod A.second)
// x == B.first (mod B.second)
// returns solution as X == ans.first (mod ans.second)
// if no solution, returns (-1, -1)
// always a good idea to keep 0 <= ?.first < ?.second (for ? : A, B, ans)
pair<ll, ll> solve(pair<ll, ll> A, pair<ll, ll> B)
{
	if(A.second == -1 || B.second == -1) return make_pair(-1, -1);
	if(A.second == 1) return B;
	if(B.second == 1) return A;
	ll g = gcd(A.second, B.second); // gcd
	ll l = A.second * (B.second / g); // lcm
	if((B.first-A.first)%g!=0) return make_pair(-1, -1); // no solution case

	ll a = A.second / g;
	ll b = B.second / g;
	ll mul = (B.first-A.first) / g;
	mul = (mul * minv(a%b, b)) % b; // this is now t
	ll ret = (mul * A.second + A.first); // n_1 t + a_1
	ret %= l; ret = (ret + l) % l; // take modulos
	return make_pair(ret, l);
}

ll Bob(vector<pint> edges){
    vector<pll> a;
	for(auto& [u, v]:edges) {
        a.push_back({u-1,v});
	}
	pll dap=a[0];
	for(ll i=1;i<a.size();i++) {
        dap=solve(dap,a[i]);
        if(dap.second>1e18) return dap.first;
	}
}

Compilation message

Bob.cpp: In function 'll Bob(std::vector<std::pair<int, int> >)':
Bob.cpp:58:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(ll i=1;i<a.size();i++) {
      |             ~^~~~~~~~~
Bob.cpp:53:17: warning: control reaches end of non-void function [-Wreturn-type]
   53 |     vector<pll> a;
      |                 ^

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1268 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1268 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1268 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -