//URAL-1100-FINAL STANDINGS

//---------------------------------
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'


bool comp(pair<int,int>a,pair<int,int>b)
{
    return a.second>b.second;
}
void sortt(map<int,int>mp)
{
    vector<pair<int,int>>v;
    for(auto it:mp)
    {
        v.push_back(it);
    }

    stable_sort(v.begin(),v.end(),comp);
    for(auto it:v)
    {
        cout<<it.first<<" "<<it.second<<endl;

    }
}
int main()
{
    map<int,int>mp;
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int x,y;
        cin>>x>>y;
        mp[x]=y;
    }
    sortt(mp);


    return 0;
}

In my AC solution I didn't use the fact that "there is no substrings in the form xyxyx" anywhere. My program even assumes the answer in this problem can be "-1", but I guess there are no such testcases in this problem because of this advanced condition.

So, could anybody tell me how this fact helps to simplify the solution? Or, maybe, anybody can prove or deny my hypotesis about "-1"? Thanks in advance!

I have always been interested in applied programming (since 9th grade), but less than an year ago I discovered a great hobby - solving competitive programming problems.

After the 200th AC, I would say This Online Judge is great, and I wish everyone motivation and good luck!

I've used this formula to solve this problem:
a(n) = 2^(b(n)-1) + a(n - c(1+b(n)))
b(n) = -1+floor(log(((n+0.2)*sqrt(5)))/log((1+sqrt(5))/2));
c(0) = 0, c(1) = 1, c(n) = c(n-1) + c(n-2)

Why this problem has 175 difficulty?
I thought it has very hard to implement solution, but to sovle it you should do what exactly said in staitment...

New tricky tests have been added to the problem.
All solutions have been rejudged. 152 authors (62% of all) lost their solved status for the problem.

import java.util.Scanner;

public class Task_2100 {
    public static void main(String[] args){
        Scanner scr1 = new Scanner(System.in);
        Scanner scr2 = new Scanner(System.in);

        int n, counter;
        n = scr1.nextInt();
        counter = n+2;
        while(n-- > 0){
            String guest = scr2.nextLine();
            String substring = "+";
            if(guest.contains(substring)){
                counter++;
            }
        }
        if(counter==13) {
            counter++;
        }
        System.out.print(counter*100);
    }
}

If you sort segments according to INCREASING length.  Then you can consider all segments one by one consecutively.  Find points belong to the current segment.  For those points current segment is the answer.
Because of the segments are sorted.

Unexpected result: the solution using z-function is O(n) but gives TLA on the 8th test. The solution doesn't pass so I will leave the code with it here. I'm wondering if it really doesn't pass the 8th test because it is too slow though is O(n), or if there's just some kind of error in my algorithm.

vi ZFunction(string &p, string &s) {
  int n = (int) p.size();
  vector<int> z(n + 1);
  for (int i = 0, l = 0, r = 0; i < n; ++i) {
    if (i <= r)
      z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && p[z[i]] == s[i + z[i]])
      ++z[i];
    if (i + z[i] - 1 > r)
      l = i, r = i + z[i] - 1;
  }
  return z;
}

  ....
  vector<int> z_func = ZFunction(s1, s2);
  vector<int> z_func2 = ZFunction(s2, s1);
  for (int i = 0; i < n; ++i) {
    if (z_func[i] == n - i && z_func2[n - i] == i) {
      cout << i;
      return;
    }
  }
  cout << "-1";

Edited by author 13.04.2023 23:25

Edited by author 13.04.2023 23:25

Edited by author 13.04.2023 23:27

Check your "MAXN" constant

I`m using vector of segments.
Everything is pretty fast, All the tests I could think of work correctly.

EDIT:
Finally, got a pretty good AC - Time: 0.234, Memory: 5 032 KB.
(The problem was that I was not monitoring for segments getting empty)

Edited by author 12.04.2023 23:40

Дайте тесты, пожалуйста

I firstly tried to solve it with Ford-Bellman algorithm, but got TL and could not make it pass. Then I found here https://e-maxx.ru/algo/min_cost_flow Levit algorithm, and it passed.

A new constraint on the input added: “It is guaranteed that any two distinct intersection or touch points of the cutting circles lay at the distance of at least 10^-3.” The tests not satisfying this constraint were corrected or removed. Some new tests were added at the same time. The time limit was adjusted to 1 sec.

All solutions have been rejudged. 23 authors lost, and 13 other authors gained the solved status for the problem.

Im an idiot
I wrote "Saturtay" instead Saturday

Edited by author 10.04.2023 02:46

After some failed attempts with O(n)=n*n/2, finally I found an O(n)=n solution.
In plain C, it took 0.09s and 1.5Mb. (just from curiosity tried the same with C# - 14MB used RAM :))

The arrays of X and Y coordinates can be sorted independently from each other.

So basically, this input:
3
1 3
2 1
3 2
will have exactly the same result (which is 2) as
3
1 1
2 2
3 3

My bad accepted, best Go solution to date

Edited by author 06.04.2023 19:36

Try this test:

-10 -1 1
-1 8 1
-7 2 1
3

Answer: 14.38

who has ideas, what test it is?