#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Thank you for participating!

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int x, y;
	cin >> x >> y;
	cout << min(x, y) << ' ' << max(x, y) << '\n';	
}
 
int main() {
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1971B - Different String

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	string s;
	cin >> s;
	bool ok = false;
	for (int i = 1; i < (int)(s.length()); i++) {
		if (s[i] != s[0]) {swap(s[i], s[0]); ok = true; break;}
	}	
	if (!ok) {
		cout << "NO\n"; return;
	}
	cout << "YES\n";
	cout << s << '\n';
}
 
int main() {
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1971C - Clock and Strings

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	string s;
	for (int i = 1; i <= 12; i++) {
		if (i == a || i == b) {s += "a";}
		if (i == c || i == d) {s += "b";}
	}
	cout << (s == "abab" || s == "baba" ? "YES\n" : "NO\n");
}
 
int main() {
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1971D - Binary Cut

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	string s;
	cin >> s;
	int res = 1;
	bool ex = false;
	for (int i = 0; i + 1 < (int)(s.size()); i++) {
		res += (s[i] != s[i + 1]);
		ex |= (s[i] == '0' && s[i + 1] == '1');
	}
	cout << res - ex << '\n';
}
 
int main() {
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1971E - Find the Car

Idea: mesanu

Tutorial

Solution

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
typedef long long  ll;
using namespace std;
 
void solve()
{
    int n, k, q;
    cin >> n >> k >> q;
    vector<long long> a(k+1), b(k+1);
    a[0] = 0;
    b[0] = 0;
    for(int i = 1; i <= k; i++)
    {
        cin >> a[i];
    }
    for(int i = 1; i <= k; i++)
    {
        cin >> b[i];
    }
    for(int i = 0; i < q; i++)
    {
        long long c;
        cin >> c;
        int l = 0, r = k;
        while(l <= r)
        {
            int mid = l+r>>1;
            if(a[mid] > c)
            {
                r = mid-1;
            }
            else
            {
                l = mid+1;
            }
        }
        if(a[r] == c)
        {
            cout << b[r] << " ";
            continue;
        }
        long long ans = b[r] + (c-a[r])*(b[r+1]-b[r])/(a[r+1]-a[r]);
        cout << ans << " ";
    }
    cout << endl;
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

1971F - Circle Perimeter

Idea: mesanu

Tutorial

Solution

#include <iostream>
using namespace std;
 
void solve()
{
    long long r;
    cin >> r;
    long long height = r;
    long long ans = 0;
    for(long long i = 0; i <= r; i++)
    {
        while(i*i+height*height >= (r+1)*(r+1))
        {
            height--;
        }
        long long cop = height;
        while(i*i+cop*cop >= r*r && cop > 0)
        {
            cop--;
            ans++;
        }
    }
    cout << ans*4 << endl;
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

1971G - XOUR

Idea: mesanu

Tutorial

Solution

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
 
using namespace std;
 
 
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, priority_queue<int>> mp;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        mp[a[i]>>2].push(-a[i]);
    }
    for(int i = 0; i < n; i++)
    {
        cout << -mp[a[i]>>2].top() << " ";
        mp[a[i]>>2].pop();
    }
    cout << endl;
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

1971H - ±1

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
 
#include <algorithm>
#include <utility>
#include <vector>
 
namespace atcoder {
namespace internal {
 
template <class E> struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    csr(int n, const std::vector<std::pair<int, E>>& edges)
        : start(n + 1), elist(edges.size()) {
        for (auto e : edges) {
            start[e.first + 1]++;
        }
        for (int i = 1; i <= n; i++) {
            start[i] += start[i - 1];
        }
        auto counter = start;
        for (auto e : edges) {
            elist[counter[e.first]++] = e.second;
        }
    }
};
 
// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
  public:
    scc_graph(int n) : _n(n) {}
 
    int num_vertices() { return _n; }
 
    void add_edge(int from, int to) { edges.push_back({from, {to}}); }
 
    // @return pair of (# of scc, scc id)
    std::pair<int, std::vector<int>> scc_ids() {
        auto g = csr<edge>(_n, edges);
        int now_ord = 0, group_num = 0;
        std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
        visited.reserve(_n);
        auto dfs = [&](auto self, int v) -> void {
            low[v] = ord[v] = now_ord++;
            visited.push_back(v);
            for (int i = g.start[v]; i < g.start[v + 1]; i++) {
                auto to = g.elist[i].to;
                if (ord[to] == -1) {
                    self(self, to);
                    low[v] = std::min(low[v], low[to]);
                } else {
                    low[v] = std::min(low[v], ord[to]);
                }
            }
            if (low[v] == ord[v]) {
                while (true) {
                    int u = visited.back();
                    visited.pop_back();
                    ord[u] = _n;
                    ids[u] = group_num;
                    if (u == v) break;
                }
                group_num++;
            }
        };
        for (int i = 0; i < _n; i++) {
            if (ord[i] == -1) dfs(dfs, i);
        }
        for (auto& x : ids) {
            x = group_num - 1 - x;
        }
        return {group_num, ids};
    }
 
    std::vector<std::vector<int>> scc() {
        auto ids = scc_ids();
        int group_num = ids.first;
        std::vector<int> counts(group_num);
        for (auto x : ids.second) counts[x]++;
        std::vector<std::vector<int>> groups(ids.first);
        for (int i = 0; i < group_num; i++) {
            groups[i].reserve(counts[i]);
        }
        for (int i = 0; i < _n; i++) {
            groups[ids.second[i]].push_back(i);
        }
        return groups;
    }
 
  private:
    int _n;
    struct edge {
        int to;
    };
    std::vector<std::pair<int, edge>> edges;
};
 
}  // namespace internal
 
}  // namespace atcoder
 
#include <cassert>
#include <vector>
 
namespace atcoder {
 
// Reference:
// B. Aspvall, M. Plass, and R. Tarjan,
// A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean
// Formulas
struct two_sat {
  public:
    two_sat() : _n(0), scc(0) {}
    two_sat(int n) : _n(n), _answer(n), scc(2 * n) {}
 
    void add_clause(int i, bool f, int j, bool g) {
        assert(0 <= i && i < _n);
        assert(0 <= j && j < _n);
        scc.add_edge(2 * i + (f ? 0 : 1), 2 * j + (g ? 1 : 0));
        scc.add_edge(2 * j + (g ? 0 : 1), 2 * i + (f ? 1 : 0));
    }
    bool satisfiable() {
        auto id = scc.scc_ids().second;
        for (int i = 0; i < _n; i++) {
            if (id[2 * i] == id[2 * i + 1]) return false;
            _answer[i] = id[2 * i] < id[2 * i + 1];
        }
        return true;
    }
    std::vector<bool> answer() { return _answer; }
 
  private:
    int _n;
    std::vector<bool> _answer;
    internal::scc_graph scc;
};
 
}  // namespace atcoder
 
 
using namespace std;
using namespace atcoder;
 
void solve() {
	int n;
	cin >> n;
	int b[3][n];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < n; j++) {
			cin >> b[i][j];
		}
	}
	two_sat ts(n);
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < 3; i++) {
			int nxt = (i + 1) % 3;
			ts.add_clause(abs(b[i][j]) - 1, b[i][j] > 0, abs(b[nxt][j]) - 1, b[nxt][j] > 0);
		}
	}
	cout << (ts.satisfiable() ? "YES\n" : "NO\n");
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

Comments (153)

Write comment?

SlavicG

6 months ago, # |

+36

🌹

→ Reply

aryanc403

+15

My post contest discussion stream

Lofts69

6 months ago, # ^ |

What if you changed thte black backlight to a light white one

lv.zheng

+25

My joke solution to problem C:

https://mirror.codeforces.com/contest/1971/submission/260436859

codex47

Bro can you explain your solution?

dimastrakhal

He converts given integers to points on plane to find the answer with geometry

I was gonna ask you to atleast give me a keyword to google. But i asked chat gpt. Only thing i understood is it's not worth it at my level. lol

Anyway, Thank you for your time.

← Rev. 2 →

e^(i*omega) produces a point in the unit circle in the complex plane. Here I use it to produce the position of 1-12 o’clock. Then, there is a triangle area formula that produce positive value if 3 points are given in counterclockwise order, negative value clockwise. So I use it to calculate the area of Δabc and Δabd. It’s obvious that c and d are on opposite of line ab iff one is positive and the other is negative.

DeadMan69

he just , gave the hands of click different coordinates on a plane , then plotted the time(points) on the given graph , then check if there is any point of intersection between the given two lines , an interesting way XD.

Bebo

Dude, you included the wrong tutorial for problem B.

marawan222

3 weeks ago, # ^ |

it's useless problem , i tried to check if a string is palinrome if it is so i can change the l[r] , l[l] elements , also if the size of the string is 1 ... here's my code which fails on the 2nd test case "jury has output that a contestant doesn't have."

int main() {
   FastIO;
   int t;cin>>t;
   while(t--){
      STR s;cin >> s;

      int l = 0 , r = s.size()-1;
      bool f = true;
      while(l<= r){
         if(s[l] != s[r]) {
            swap(s[l],s[r]);
            f = false;break;
         }
         l++;r--;
      }
      if(f) cout <<"NO\n";
      else if(!f || s.size() == 1){
         cout << "YES\n";
         cout << s<<endl;
      }
   }


}

justlm

problem b editorial for now is an editorial of an old div4b problem, fix pls

upd1: fixed now

Avik_AB17

Too Fast!

Ankit_singh_sisodya

← Rev. 5 →

https://mirror.codeforces.com/contest/1971/submission/260448426

-> this is giving out of bound

https://mirror.codeforces.com/contest/1971/submission/260447515

-> this is not giving out of bond

Both code are same,, just the writing style is different..

Why is this happening?? Thanks in advance..

flamestorm(could you plz help sir)

← Rev. 3 →

The difference lies in how division is performed: the first snippet directly divides by a variable (speed) that could be close to zero, risking a division by zero or resulting in large values leading to out-of-bounds errors when accessing the 't' vector, while the second snippet avoids this issue by rearranging the calculation to use multiplication and division together.

SuperMo

the second code that passed should get out of bound

he is using upper bound take for example this case 10 1 1 10 10 10

it should give RE but it's not because I tried to hack so why ??

The second code is avoiding the expected out-of-bounds error because it decrements the index i after upper_bound, making it within bounds. However, this behavior is unreliable and could lead to issues with different inputs or compiler optimizations.

he decrements the index i but he is using (i+1)

In the second code, even though the index 'i' is decremented after upper_bound, it's still used to access t[i], which could lead to accessing an out-of-bounds element since i is decremented but used as 'i+1'. This behavior is indeed a vulnerability in the code, which could lead to unpredictable results or runtime errors, depending on the input.

https://mirror.codeforces.com/contest/1971/submission/260423806 This friend of mine did the same thing using another vector but his code didn't show any kind of this behaviour

This code ensures that mid always points to the correct segment in the array 'a', preventing out-of-bounds issues when accessing elements from 'a' and 'b'. Therefore, the code doesn't exhibit the same behavior as the previous codes.

The first code also decrement i to prevent out of bound.. And, I said the division by smaller number logic is invalid since he did the same thing...

You're correct. I apologize for that. Both the first and second snippets decrement the index i to mitigate the risk of accessing out-of-bounds elements. Additionally, you rightly pointed out that the division by a smaller number logic doesn't apply since both codes essentially use the same approach.

In that case, it seems that the difference in behavior between the two codes might be due to other factors, such as input data or compiler optimizations

Input data is same brother

weird

tickbird

took 30 min to solve F+G, still have no idea how I got WA from E 260451462

too bad actually

Solutions that use floating points will eventually get hacked.

green-eyeliner

please tell me why this is not getting accepted but (PROBLEM E) long long ans = brr[it] + ((drr[i]-arr[it]) / ((arr[it+1]-arr[it])/(brr[it+1]-brr[it])));

this is accepted? how? long long ans = brr[it] + (drr[i]-arr[it]) * (brr[it+1]-brr[it])/(arr[it+1]-arr[it]);

260452416 260452100

please, put your code in spoiler next time, or at least on different lines.

from what i can see, in the first one you should have used floating point arithmetic, but it would be a bad idea, cuz solutions with floating point are getting hacked now.

the second one just makes your original formula compatible with integer arithmetics in c++, so it works just right

I am sorry, for the bad structure of the comment, will do the needful next time.. "the second one just makes your original formula compatible with integer arithmetics in c++, so it works just right" how you know that, like how can I think like that during the contest.

try to just simplify formula as mush as you can (and also try to use less division), that's what i usually do

thankyou very much :)) wishing you loads of +ve delta

thank you!

oomphy

← Rev. 10 →

hey, I am not getting why i am getting TLE for the same problem 261422309. I even implemented the same binary search as the official solution

in the binary search function, every time that you use it, you create a new copy of a vector. what you should do instead is pass it by reference, just changing the vector v to vector &v should work

here is your solution when vector is passed by reference 261565356

Never knew making copies would take up so much time. Thank a lot mate.

Misika16483

Same problem and really learned a lot! Thanks!

logi_11

yeah similar problem same testcase failed.

tnsnz

void main() { long long s = 999999937; long long a = (double)1.0 / s * s; long long b = s * 1 / s; printf("%lld %lld", a, b); }

formidablechief27

Detailed Video Editorials (BCDEFG)

https://www.youtube.com/playlist?list=PLbAEGNVuy98kfnqOz26QPV4cSpj9j-3tY

Language — Hindi

xeureka

nice editorial but why does always with c++ why dont in python or other languages

aradyaShetty

gengu

its better for the purpose ig

Intuition2.0

Can anyone explain me please(with reference to problem E) — as the answer needs to be rounded off to nearest integer value...so let say total comes out to be like 1.6 then the rounded off answer wouldn't be 2 instead of 1. And without using round() 1 will be the ans, then how it's correct without using round function? Am i misunderstood the word rounded *down(instead off) which means to always round off to floor value? But i sumbitted with using round() also..and why ac for that?

i think that's just a typo, because russian statement says it should be rounded down

Then why it got also ac with using round() In case like 1.6 it gives 2 but the ans would be 1 yeah?

Now i got the clarity. I used int and before rounding off it already converted into int .so there is no effect of round() in this situation..lol blunder by me

saelcc03

X.MAN

I wrote this code for problem F During the contest.. But now I really have no idea way it works !!!!!!

void calculate() {
    int r;
    cin >> r;
    int ans = 2;
    for(int x = -1*r; x <= r; x++) {
        ans += ((int)sqrt((r+1)*(r+1)-x*x-1)-(int)sqrt(r*r-x*x-1))*2;
    }   
    cout << ans << endl;
}

There is a case when r*r-x*x-1 becomes negative and then sqrt(negative) !!

I didn't notice that during the contest but I am really surprised to see it works!

the second thing is why the answer is 2 ? when I wrote this weird solution I noticed that it get the write answer — 2 so I added two to the answer

Very weired

Dell_Know

1 . Yes, $$$r^2 - x^2 - 1$$$ becomes $$$-1$$$ when $$$x = r$$$, then it will become -2147483648 (saw from code), but then you multiply it by 2, so it becomes 0 (because of the overflow).

You can add this in your loop to check it out for yourself.

cout << x << " " << (int)sqrt(r*r-x*x-1) << " " << (int)sqrt(r*r-x*x-1)*2 << endl;

2 . It comes from first (why you need to add 2). When $$$x = ±r$$$, you have $$$\sqrt{2r} - 0$$$ instead of $$$\sqrt{2r} - (-1)$$$, so you loose 1 point for both $$$x = r$$$, and $$$x = -r$$$.

Very helpful. Thanks alot

par4dox

5 months ago, # ^ |

why is his solution even working I don't understand the maths behind it ? didn't it just mean imaginary radius ?

haribooshan2003

In the Editorial Implementation for the problem F, when we say the overall answer is the answer per quadrant multiplied by 4, aren't we over-counting at the edges of the semi-disc (like x=0 or x=r) ?. Could anyone help figure out what I might be missing. Thanks.

xksark

We have counted at x = 0, but not at h = 0 (in second while statement there is h > 0 which ensures that we are not crossing x-axis).

Didn't see that. That's slick! Thanks!

Six_Seconds

Shouldn't this editorial be published after the end of hacking phase? [In Educational Rounds and Div3s, I usually don't see Editorials to be published before the end of Hacking Phase]

This is my solution for G if using maps, if you don't know priority_queue .

Spoiler

void solve(){
    read(n);
    vi v(n); read(v);
    map<int,pair<vi, vi>> mp;
    fori(i,n){
        mp[v[i]>>2].ff.pb(v[i]);
        mp[v[i]>>2].ss.pb(i);
    }
    vi ans(n);
    for(auto e: mp){
        sort(all(e.ss.ff));
        fori(i, e.ss.ff.size()){
            ans[e.ss.ss[i]] = e.ss.ff[i];
        }
    }
    ps(ans);
}

schrodingers_cat00

I learnt programming a month ago. I gave my first contest(944 div.4) yesterday n I solved only 3 problems. I read that div.4 is rated for unrated players. But my account is still unrated. can anyone explain why? Why I didnt get any rating?

sultansea

raiting change will came after open hacks whic is 12 hours, and then system testing, which is also 4-5 hours, so wait

fat_gladiator1712

260473966 why is this failing? I cant seem to find the issue.

DarkS0uls

res = b[prevdist] + (d - a[prevdist]) * ((b[prevdist + 1] - b[prevdist]) / (a[prevdist + 1] - a[prevdist])); is wrong since you do the division first, which would lose precision.

correct version: res = b[prevdist] + (d - a[prevdist]) * (b[prevdist + 1] - b[prevdist]) / (a[prevdist + 1] - a[prevdist]);

mash97

Learned this three things: 1. simplifying the equation so that division operations are less resulting less floating point errors. (Though not much experienced in this, I'll be glad to accept tips!) 2. precedence (* comes before /) 3. associativity (/ comes before *)

Thanks a lot, your comment helped!

feixinbai

it run well and output correct answer in my c++ ide ,but wrong on test 31, 260475302

Neev4321

In C, you say "Below is the shortest solution we know of". What about my solution? https://mirror.codeforces.com/contest/1971/submission/260294806

← Rev. 4 →

For Problem C 1971C - Clock and Strings, We can:

1.Perform a,b,c,d = min(a,b), max(a,b), min(c,d), max(c,d)

2.Check if a<c<b and !(c<b<d) then YES else NO

notSharp

interesting , can u show ur submission ?

Actium

If anyone is interested in solving problem H without fully implementing 2-SAT algo, here is a solution.

-40_degrees

Those who used float/double in E ------------------> :(

greentree888

Then what to use there & why not use double/float?

Thanks

There has been a lot of discussion on this. Check out the discussions on this blog, and you'll understand. It's actually about precision errors that occur when you convert to double/float.

chrisTris

Got Hacked in "E — Find the Car" due to unnecessary cast to double :(

Test case

1
1000000000 2 1
999999998 1000000000
999999999 1000000000
999999997

Harman001

my submission got hacked it gave wrong answer on test case 21 but when i run that test case on my ide other than that of cf it is giving the expected output . Can somebody help https://mirror.codeforces.com/contest/1971/submission/260487849

_Kee

You are given the whole input of TC21 and it's easy to calculate the real answer by hand, so you should be able to debug what went wrong in your code. The expected answer for the fourth query is: $$$\displaystyle \frac{45 \cdot 2}{6} = 15$$$. Your code produces inaccurate results due to the use of double.

Basically, you shouldn't use double in this problem. It's very hard to make calculation using double right (there are more tricky edge cases; see hacks). It's possible to solve this problem with just integer arithmetic, which gives precise answers.

mega_bot

For someone who need a small hack test case for E

answer is 29, you might get 28 due to precision errors.

WizzyRocky

in problem F if we can implement a function g that returns the number of points that have a distance d<r then the answer is g(r+1)-g(r) this function can easily be made with binary search this is my submission 260491421

Aditya8676

In Problem E ,I submitted the following code : My Submission

but it gives wrong answer on test case : 1 6 1 1 6 45 2

the expected output is 15 but my code's output is 14

When i debug my code, i found that whole error occurs in the line long long ans=floorl(time); bcoz the value of time before was 15 but after taking floorl it became 14.I don't understand why this is happening on my system and also on online judge.Is this a bug of C++ 20?? or i have done something wrong in my code.I have also used fixed<<setprecision(0) to avoid printing of answer in scientific notation like 1e9 instead of 1000000000 . But it does not affect my answer but floorl does. Kindly help me out and explain this unexpected behaviour of floorl which can be used for long double numbers as per documentation.

The value of time before floorl is 14.999999999999999999, so floorl(time) is 14. Floating point arithmetic is inaccurate by design, so this is expected behavior.

Karim__2

what best practice should we follow when dealing with floating point arithmetic.

Ok,got it.Thanks.But don't understand while debugging why it shows time 15 instead of 14.99999999 .

When cout/cerr prints a floating point numbers, the default precision is only 6 digits (IIRC), which is insufficient for double / long doubles. To get sufficiently accurate representation, use:

cout << setprecision(30) << time << '\n';

cout << format("{}\n", time);

(the latter requires C++20).

Thanks,very informative.

I don't know why but changing ((dis-a[ind-1])/speed) to

((dis-a[ind-1])*(b[ind]-b[ind-1]))/(a[ind]-a[ind-1]); works

Can someone prove why it's working ?

smit_384

double x=1/3; double y=3; int ans=(floor)(x*y); cout<<ans<<endl;

see this example .33333 * 3 == .9999999 that will round off to 0.

you can't trust doubles, there can be errors. better way would be this

Can someone explain why this is not working ?

I thought long double's precision is enough .

submission : 260494210

Muhammad_Aneeq

flamestorm can you give solution without using atcoder library of problem H??

i wrote my own 2-sat in H after contest, you can look at my solution: 260463835

Ramim19

Here i got a shorter solve of problem C 260325595

flamestorm

Nice

Fork512Hz

Problem F reminded me of my Computer Graphics course, where we discussed how to draw a circle efficiently on the screen. (It involves avoiding FP computation and replacing multiplication with addition.)

So my solution works as follows. Let point P start at $$$(0, r)$$$. For every step, checks if $$$P$$$ falls in the range. Then, P moves to the right 1 unit, and if $$$|OP| \ge r+1$$$, revert the previous move and move P down 1 unit instead. Repeat until you reach $$$(r, 0)$$$, and multiply the answer by 4.

Code

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<utility>
#include<vector>
#include<cmath>
using namespace std;
typedef pair<long long, long long> pii;
typedef vector<long long> vint;
typedef long long ll;
const long long N = 500100;
inline ll dist(ll x, ll y)
{
	return x*x + y*y;
}
int main()
{
    int z;
    cin >> z;
    while(z--){
		ll n;
		scanf("%lld", &n);
		ll x = 0, y = n;
		ll ans = 0;
		while(y > 0)
		{
			ll d2 = dist(x, y); 
			if(d2 >= n*n && d2 < (n+1) * (n+1)) // Not the fastest!
				ans++;
			if(dist(x+1, y) >= (n+1) * (n+1))
				y--;
			else
				x++;
		}
		printf("%lld\n", ans<<2);
    }
 	return 0;
}

This algorithm works because the width is 1. The reason why CG introduced this algorithm is that it never requires calculating the $$$|OP|^2$$$ by performing 2 multiplications, but you can instead calculate the increment of $$$|OP|^2$$$ in O(1) additions for each iteration.

gtg321

this is my first contest on codeforces...can anybody tell me why i don't get the score yet? i did particitate in the contest during the time it was held.

the contest is now retested using tests included in hacks. after this retesting phase you will get your rating

DuongForeverAlone

Could someone explain for me this statement from editorial of H:

at least 2 of (x,y,z) are true ⟺ at least one of (x,y) is true, at least one of (y,z) is true, and at least one of (z,x) is true.

I mean, without using truth table

0 true variables is obvious

if only one variable is true (let it be $$$x$$$) is true, then 2 out of 3 statements will evalutate to true becuase $$$x$$$ is present in two equations.

but if you turn two variables true (let them be $$$x$$$ and $$$y$$$), then all 3 equations will evaluate to true (2 of which because of variable $$$x$$$ and another one because of variable $$$y$$$ which we couldn't use before)

It's tedious but you can obtain that by using the distributive law of boolean logic: $$$a \land (b \lor c) = (a \land b) \lor (a \land c)$$$ and $$$a \lor (b \land c) = (a \lor b) \land (a \lor c)$$$, where $$$\land$$$ means logical "and" and $$$\lor$$$ means logical "or".

First, the condition "at least two of x, y, z are true" can be translated to: $$$(x \land y) \lor (y \land z) \lor (z \land x)$$$. What we want to prove is $$$(x \land y) \lor (y \land z) \lor (z \land x) = (x \lor y) \land (y \lor z) \land (z \lor x)$$$.

Let's consider just the first two terms. By the distributive law, we get $$$(x \land y) \lor (y \land z) = (x \lor (y \land z)) \land (y \lor (y \land z)) = (x \lor y) \land (x \lor z) \land (y \lor y) \land (y \lor z)$$$. Since $$$y \lor y = y$$$, and $$$y$$$ must be true in this conjunction, $$$x \lor y$$$ and $$$y \lor z$$$ are always true, thus they are redundant and can be removed. Therefore we get: $$$(x \land y) \lor (y \land z) = (x \lor z) \land y$$$.

You can derive $$$((x \lor z) \land y) \lor (z \land x) = (x \lor y) \land (y \lor z) \land (z \lor x)$$$ by expanding the expression in a similar manner. I leave this as your homework because I've written too much $$$\TeX$$$ s already :)

Dominater069

Forward implication is trivial since atmost 1 variable can be false.

Backward implication is also trivial. Assume 2 are false, wlog let them x, y. Then clearly there are 2 things wrong in (x, y) pair. Contradiction

Rujul

Why am i gettng wrong answer on test case 6 in F, where the value of r is 1e5. Submission link and when I am printing it for the 1e5 case, it gives correct answer. Submission link for accepted

dev.22622

Int the problem F wouldn't be the area of the region be 2*pie*r + pie

dhamdhereshriram

-11

In problem E

include<bits/stdc++.h>

using namespace std; // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds;

// #define ordered_set tree<int, null_type,less, rb_tree_tag,tree_order_statistics_node_update>

define f0r(a, b) for (long long a = 0; a < (b); ++a)

define f1r(a, b, c) for (long long a = (b); a < (c); ++a)

define f0rd(a, b) for (long long a = (b); a >= 0; --a)

define f1rd(a, b, c) for (long long a = (b); a >= (c); --a)

define ms(arr, v) memset(arr, v, sizeof(arr))

define send {ios_base::sync_with_stdio(false);}

define help {cin.tie(NULL); cout.tie(NULL);}

define fix(prec) {cout << setprecision(prec) << fixed;}

define mp make_pair

define all(v) v.begin(), v.end()

define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}

define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}

define vsz(x) ((long long) x.size())

typedef long long ll; typedef long double lld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector vi; typedef vector vl; typedef vector vpi; typedef vector vpl; typedef long long ll; typedef unsigned long long ull; typedef long double lld;

void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << ''' << x << ''';} void __print(const char *x) {cerr << '"' << x << '"';} void __print(const string &x) {cerr << '"' << x << '"';} void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << '}';} void _print() {cerr << "]\n";} template <typename T, typename... V> void print(T t, V... v) {_print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

ifndef ONLINE_JUDGE

define debug(x...) cerr << "[" << #x << "] = ["; _print(x)

else

define debug(x...)

endif

void solve() { // TODO: Add your code here int n,k,q; cin>>n>>k>>q; vector a(k+1); vector b(k+1);

a[0]= 0;
b[0]= 0;
for(int i=1;i<=k;i++){
    cin >> a[i];
}


for(int i=1;i<=k;i++) {
    cin>>b[i];

}

while(q--){
    int d;
    cin>>d;
    int it = lower_bound(a.begin(), a.end(), d) - a.begin();

    double t2,x2;
    if(d==a[it]){

            cout << b[it] << ' ';
            continue;

    }
    else it--;

    ll ans = b[it];
    ll t = ((d-a[it])*(b[it+1]-b[it])) / (a[it+1]-a[it]);
    // if(ans - int(ans) >= 0.5) ans = int(ans + 1);
    // else ans = int(ans);
    cout << ans + t << ' ';
}
cout << '\n';

}

int main() { #ifndef ONLINE_JUDGE freopen("Error.txt", "w", stderr); #endif send help; int _t;cin>>_t;while(_t--) solve(); return 0; }

ABOVE SOL got accepted

void solve() { // TODO: Add your code here int n,k,q; cin>>n>>k>>q; vector a(k+1); vector b(k+1); vector dp(k+1, 0); a[0]= 0; b[0]= 0; for(int i=1;i<=k;i++){ cin >> a[i]; }

for(int i=1;i<=k;i++) {
    cin>>b[i];

}

while(q--){
    double d;
    cin>>d;
    int it = lower_bound(a.begin(), a.end(), d) - a.begin();

    double t2,x2;
    if(d==a[it]){

            cout << b[it] << " ";
            continue;

    }
    else it--;

    ll ans = b[it];
    ll t = ((d-a[it])*(b[it+1]-b[it])) / (a[it+1]-a[it]);
    // if(ans - int(ans) >= 0.5) ans = int(ans + 1);
    // else ans = int(ans);
    cout << ans + t << " ";
}
cout << '\n';

ABOVE got rejected

only difference is the double d and int d in the while loop query can anyone tell me whats wrong

I got hacked my initial cases were passed correctly

Pro tip :always share your code as a submission link or no one is reading it.

like this 260430183

AbdulRahmanLuai

What is the best way to deal with precision issues when using floating points like in problem E? MY SOLUTION

Thanks in advance

visheshvaidya24112004

My very intuitive solution of problem c : 260585157

Fume

Can anyone help me indentifying why my code is giving runtime error for this following code in Problem G: "https://mirror.codeforces.com/contest/1971/submission/260600724"

llc5pg

I modified your submission in 2 places. Now it can AC. See submission

Hey thanks, it got an AC. I removed the equality sign from comparator and got correct answer, but still can't figure out why removing equality sign from comparator got an AC.

AkiLotus

(Disclaimer: my claim has a little bit of rule of thumbs and informal terminologies here, since I was half unsure, half wanting to simplify the topic)

Normally for programming languages, defined comparator that takes two entities $$$a$$$ and $$$b$$$ should return true if and only if $$$a$$$ should be placed before $$$b$$$, and it will look upon those comparisons returning true to dictate the final order of the list/array.

Thus if you consider $$$a \le b$$$ as true, and in fact $$$a = b$$$, comparator will take both compare(a,b) and compare(b,a) as true, thus sending those two entities into an endless loop of placing one before another. This part is an undefined behavior, that different compiler implementations will have different responses to this (and in this exact case, most implementations will break your code, either through TLE or RTE).

Removing equal sign will break that loop, ensuring that the array/list can be sorted in a deterministic way in the comparator's viewpoint.

Yes, your point makes lot of sense but if both the "compare" functions should return true, then the compiler should ideally make both the elements stay at their own place. Why it should end in an infinite loop ?

Like it can also occur in cases when sorting an array with all elements equal

This part, I apologize, I can't explain further, coz' I also don't know in-depth. It's not really supposed to be compiler's doing at this point, but how the sorting algorithm in the library works internally, and it is over my head (usually in a programming language, sorting algorithm is a hybrid of things, so without digging in I can't tell for sure).

A comparator (in c++ atleast) is supposed to return true IFF a should be placed before b. This is the standard of the language.

By returning true when a = b, you are basically telling the compiler to put a before b, and also to put b before a.

arghya_G

-8

https://mirror.codeforces.com/problemset/submission/1971/260624825

can anyone hep me how to deal with this error (wrong output format Expected integer, but "1e+009" found)

thank you

cout << int(b[k]) << " ";

also change (b[i + 1] - b[i]) / (a[i + 1] - a[i]) * (c - a[i]); to (c - a[i])*(b[i + 1] - b[i]) / (a[i + 1] - a[i]);

Kunal_Kashyap

why are we using -a[i] in editorial soln of problem G ` ~~~~~ mp[a[i]>>2].push(-a[i]); ~~~~~

KIteREtsU__

So that priority queue gives min value instead of max value.

yyashm1491625

~~~~~

using namespace std; const int M = 1000000007;

void hello() { int n; cin >> n; vector a(n); map<int, deque> f; for(int i = 0; i < n; i++) { cin >> a[i]; f[a[i] >> 2].push_back(a[i]); } for(int i = 0; i < n; i++) { if(f[a[i] >> 2].size() > 1) { sort(f[a[i] >> 2].begin(), f[a[i] >> 2].end()); } } for(int i = 0; i < n; i++) { cout << f[a[i] >> 2].front() << " "; f[a[i] >> 2].pop_front(); } cout << "\n"; }

int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t = 1; cin >> t; while(t--) { hello(); } return 0; }~~~~~

can anyone plz help me with this, getting tle on test 13

ogfemboy

can anybody tell me what is wrong with my code, its giving wa on test case 3

#define int long long 
const int maxn=1003;
vector<int> adj[maxn];
vector<int> adj_t[maxn];
vector<int> topo;
int colors[maxn];
bool visited[maxn];

void dfs(int node)
{
    visited[node]=1;
    for(auto it:adj[node])
    {
        if(!visited[it])
        dfs(it);
    }
    topo.pb(node);
}
void dfs2(int node,int color)
{
    visited[node]=1;
    colors[node]=color;
    for(auto it:adj_t[node])
    {
        if(!visited[it])
        dfs2(it,color);
    }
}
void solve(){

    int n;
    cin>>n;
    for(int i=0;i<=2*n+2;i++)
    {
        adj[i].clear();
        adj_t[i].clear();
    }
    topo.clear();
    memset(colors,0,sizeof(colors));
    vector<vector<int>> arr(3,vector<int>(n));
    
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<n;j++)
        cin>>arr[i][j];
    }
    for(int i=0;i<n;i++)
    {
        int x1=arr[0][i];
        int x2=arr[1][i];
        int x3=arr[2][i];
        int b1=0,b2=0,b3=0;
        if(x1<0) b1=1;
        if(x2<0) b2=1;
        if(x3<0) b3=1;
        // cout<<n*(1-b1)+abs(x1)<<".."<<x1<<endl;
        adj[n*(1-b1)+abs(x1)].pb(n*b2+abs(x2));
        adj_t[n*b2+abs(x2)].pb(n*(1-b1)+abs(x1));
        adj[n*(1-b2)+abs(x2)].pb(n*b3+abs(x3));
        adj_t[n*b3+abs(x3)].pb(n*(1-b2)+abs(x2));
        adj[n*(1-b3)+abs(x3)].pb(n*b1+abs(x1));
        adj_t[n*b1+abs(x1)].pb(n*(1-b3)+abs(x3));
    }
    // for(int i=1;i<=2*n;i++)
    // {
    //     cout<<i<<".";
    //     for(auto it:adj[i])
    //     cout<<it<<" ";
    //     cout<<endl;
    // }
    memset(visited,false,sizeof(visited));
  
    for(int i=1;i<=2*n;i++)
    {
        if(!visited[i])
        dfs(i);
    }
    memset(visited,false,sizeof(visited));
    reverse(topo.begin(),topo.end());
    int color=0;
    for(int node:topo)
    {
        if(!visited[node])
        dfs2(node,color++);
    }
    // for(int i=1;i<=2*n;i++)
    // cout<<colors[i]<<" ";
    // cout<<endl;
    for(int i=1;i<=n;i++)
    {
        if(colors[i]==colors[i+n])
        {
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        //write code here
        solve();
    }
    return 0;
}

for clarification i got my mistake for every clause A v B

not A -> B not B -> A

both these edges should be added but i just added not A -> B

harsh_bamane17

How to correct this precision error? 260750048 ```

...

void solve() {
ll n,k,q; cin>>n>>k>>q; vectora(k),b(k);

for(int i=0;i<k;i++){
        cin>>a[i];       
    }

    for(int i=0;i<k;i++){
        cin>>b[i];       
    }
    a.insert(a.begin(),0);
    b.insert(b.begin(),0);
    vector<float>speed;
    k++;
    for(int i=1;i<k;i++){
        ll dis=a[i]-a[i-1];
        ll time = b[i]-b[i-1];
        float spd = dis/(float)time;
        speed.push_back(spd);
    }
    speed.insert(speed.begin(),0);

    while(q--){
        ll num;
        cin>>num;
        ll idx = lower_bound(a.begin(),a.end(),num)-a.begin();
        ll total= a[idx]-a[idx-1];
        if(num==a[idx]){
            cout<<b[idx]<<" ";
            continue;
        }
        else{

            ll rem = total - (a[idx]-num);
            double tm = static_cast<double>(rem) / speed[idx];
            cout << fixed << setprecision(10);
            cout << static_cast<ll>(b[idx-1] + tm) << " ";

        }
    }
    cout<<nl;

first of all never use float always use double or long double .But in this problem that is not enought.

just write the whole formula tm = rem * (b[idx+1]-b[idx])/(a[idx+1]-a[idx])

Thanks, it all worked!

walkieme

Hey, a question regarding problem G (in C++). My code gives TLE when using unordered_map, but is accepted when using map. Why is it so? Most of the time I am using unordered_map and in this case, although the solution is correct, it is a bit of a bummer that it gives TLE (because how would I know that the problem is the use of unordered_map).

I'd assume that there are some tests (either from main or hacking phase) that exploits the hashing algorithm of unordered_map, causing enough collisions to make its operations $$$\mathcal{O}(n)$$$ instead of the average $$$\mathcal{O}(1)$$$.

map is $$$\mathcal{O}(\log n)$$$ constantly so such tests are harmless to it.

yugmaheshwari2004

For C can anyone find error in my code https://mirror.codeforces.com/contest/1971/submission/260905825

Mostly precision errors to me.

A few rules of thumbs:

Ditch float, use double and long double when needed. float's fp16 nature has very low precision.
Only use floating point numbers when there are no alternatives. Here, as the problem only requires the answer rounded down, you can do everything with int/long long, just make sure you do the correct calculating order (there is only one dividing operation per query, so do it last).

Jsanchez1011

Why in the four testcase of problem H, the case 6 1 3 -6 2 5 2 1 3 -2 -3 -6 -5 -2 -1 -3 2 3 1

Say no?, the array [1, 1, 1, 1, 1, -1] doesn't works?

laozhu1234

col3 is -6 -2 -3, with array [1, 1, 1, 1, 1, -1], it would be 1 -1 -1. Sort them, we find the middle row is -1.

'each column', yeah i dont realized that until now, thanks a lot for answering and your help :D

nanhkhang23ti

6 1 3 -6 2 5 2 1 3 -2 -3 -6 -5 -2 -1 -3 2 3 1 explain this test help me

I think it cout YES with [1,1,1,1,1,-1]

The Sort Is in each columna, no the all of the matriz, so su need each columna only have a -1, ( the case 4, in third column dont work with [1, 1,1,1,1,-1], because you have un that column 1, -1, -1, AND sorted, you have -1, -1, 1, where you have a -1 in the middle and can't win)

Abdus_Selim

Amazing tutorials and solutions. Thanks.

yuanhaok

For G, why I use map is correct, but when I use unordered_map is timeout?
261159622

RomanLeshchuk

Could please someone explain me what is wrong with my 2-SAT implementation for the problem H? My attempt fails on the test 3 with wrong answer: https://mirror.codeforces.com/contest/1971/submission/261300539. I guess there should be a problem somewhere in a Tarjan's algorithm implementation, because earlier I used less optimized way to find SCC, and it worked up to test 7, where it timed out.

Okay, I just tried to rewrite the code, and now my solution passes. If someone is interested in another correct code for problem H: https://mirror.codeforces.com/contest/1971/submission/261434608

sla7Ahmed

My second solution to clock & string

int n;
int main()
{
	cin >> n;
	for (;n; n--)
	{
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		if (a < b) swap(a, b);
		if (c < d) swap(c, d);

		int diff1 = a - c;
		int diff2 = b - d;

		if (!((diff1 > 0) ^ (diff2 > 0)) && ((c > b && diff1 > 0) or (a > d && diff1 < 0))) {
			cout << "YES" << endl;
		}
		else { cout << "NO" << endl; }
	}
	return 0;
}

tn757

Here's a neat little solution for F, I observed that all points on the circle perimeter are touching one another, so we can just "trace" the circle and bfs every point within the correct distance. Very easy solution when you do it this way.

void solve(){
    int r;
    cin >> r;
    map<array<int, 2>, int> vis;
    queue<ai> q;
    q.push({0, r});
    int ans = 0;
    while (!q.empty()) {
        auto [i, j] = q.front();
        q.pop();
        if (vis[{i, j}]++) continue;
        int sq = sqrt(i*i+j*j);
        ans += (r <= sq && sq < r+1);
        for (int a = -1; a <= 1; a++) {
            for (int b = -1; b <= 1; b++) {
                int new_sq = sqrt((i+a)*(i+a) + (j+b)*(j+b));
                if (new_sq >= r && new_sq < r+1) q.push({i+a, j+b});
            }
        }
    }
    cout << ans << endl;
}

mayank.singh19

Hi All,

Can anyone help why this solution is incorrect for problem F

public static void main(String[] args) {
    MyScanner sc = new MyScanner(); 
    out = new PrintWriter(new BufferedOutputStream(System.out));

    int test = sc.nextInt();
    while (test-- > 0) {
      long n = sc.nextLong();

      long count = 0;
      for (long i = n; i > 0; i--) {
        long high = numHigh(((n + 1L) * (n + 1L)) - (i * i));
        long low = numLow((n * n) - (i * i));
        count += high - low + 1L;
      }

      out.println(count * 4);
    }

    out.close();
  }

  public static long numHigh(long sum) {
    long sqrt = (long) Math.sqrt((double) sum);
    return sqrt * sqrt == sum ? sqrt - 1L : sqrt;
  }

  public static long numLow(long sum) {
    long sqrt = (long) Math.sqrt((double) sum);
    return sqrt * sqrt == sum ? sqrt : sqrt + 1L;
  }

anshs10

this was nice contest.

Kai_007

Solution for G is damn Good!

nhbao2207

https://mirror.codeforces.com/contest/1971/submission/262898473

Here is my solution for problem C. I think it is much shorter and easier to understand!

Zanderxx

is the clock string soln correct bro?

MiyawakiSakura

Why can't D be solved by counting number of "01"s?

for example, grader says 101 must need 3 pieces, but you can cut like this 1|01 then arrange into 01|1, which shows you only need 2 pieces

vspinei

My solution for problem G is very similar to the one in the editorial, however it didn't pass until I switched from using unordered_map to just map.

5 months ago, # |

My solution to C with neural network: 265483456

The parameters are trained with Tensorflow and then I hand-craft the code to run this model because we cannot import numpy on cf.

benjellounelghali99

WoW , well done

Hey , In problem G I forget about lexicographical order and i don't see something in the code that assures it , why is it working ?? We didn't even add a comparator on the pq ?

penrosecat

6 weeks ago, # ^ |

The definition of lexicographical order for arrays in the question just devolves to regular sorted arrays. Lol. I also fell for it. Lesson learnt, read the problem carefully.

BeanBurrito

getting TLE on H: https://mirror.codeforces.com/contest/1971/submission/268388372

using an adjacency list to construct the implication graph, then running DFS(x, !x) and DFS(!x, x) for each variable x.

EDIT: I stopped resetting my visited vector in between DFSs. Unsurprisingly, this made my code run faster, but I'm not sure how it got accepted. Shouldn't having nodes marked as visited (which actually haven't been visited) result in WA?

convergent

Sean6

1971H - ±1 can use bruteforce solution to solve (O(N^2)) 269428997

ysyswd

4 months ago, # |

problem E,i can never know what mistake i've made! HELP![submission:274632531]

TanJWcode

3 months ago, # |

I have no idea that int keys in python dictionary cost so much time in problem G

279007510 used int keys and got TLE

279008366 used str keys and only used half the time

3 weeks ago, # |

my i know why my code here isn't passing the 2nd test case in B?

mesanu's blog

include<bits/stdc++.h>

define f0r(a, b) for (long long a = 0; a < (b); ++a)

define f1r(a, b, c) for (long long a = (b); a < (c); ++a)

define f0rd(a, b) for (long long a = (b); a >= 0; --a)

define f1rd(a, b, c) for (long long a = (b); a >= (c); --a)

define ms(arr, v) memset(arr, v, sizeof(arr))

define send {ios_base::sync_with_stdio(false);}

define help {cin.tie(NULL); cout.tie(NULL);}

define fix(prec) {cout << setprecision(prec) << fixed;}

define mp make_pair

define all(v) v.begin(), v.end()

define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}

define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}

define vsz(x) ((long long) x.size())

ifndef ONLINE_JUDGE

define debug(x...) cerr << "[" << #x << "] = ["; _print(x)

else

define debug(x...)

endif

include<bits/stdc++.h>

define f0r(a, b) for (long long a = 0; a < (b); ++a)

define f1r(a, b, c) for (long long a = (b); a < (c); ++a)

define f0rd(a, b) for (long long a = (b); a >= 0; --a)

define f1rd(a, b, c) for (long long a = (b); a >= (c); --a)

define ms(arr, v) memset(arr, v, sizeof(arr))

define send {ios_base::sync_with_stdio(false);}

define help {cin.tie(NULL); cout.tie(NULL);}

define fix(prec) {cout << setprecision(prec) << fixed;}

define mp make_pair

define all(v) v.begin(), v.end()

define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}

define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}

define vsz(x) ((long long) x.size())

ifndef ONLINE_JUDGE

define debug(x...) cerr << "[" << #x << "] = ["; _print(x)

else

define debug(x...)

endif

include <bits/stdc++.h>