Блог пользователя Ayariyanam

Автор Ayariyanam, история, 5 часов назад, По-английски

There is an inconsistency in output in my system and codeforces environment. Following is my implementation. https://codeforces.me/contest/2037/submission/292083626 Test case 1: 2 1 4 5 3 3 my output in codeforces is shown as 2 2 but when I run it else anywhere (online and my machine) its giving 1 4.

#include <bits/stdc++.h>
    using namespace std;

    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            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);
        }
    };

    void solve(){
        int len;
        cin>>len;
        vector<int> v(len);
        for(auto& x: v) cin>>x;
        int target=len-2;
        unordered_map<int, int, custom_hash> umap;
        for(auto x: v){
            if (target%x!=0) continue;
            umap[x]++;
        }
        for (auto& it: umap){
            int num = it.first;
            int second=target/num;
            if ((second==num) && (it.second>1)){
                cout<<num<<" "<<num<<endl;
                return;
            }
            else if (umap.find(second) !=umap.end()){
                cout<<num<<" "<<second<<endl;
                return;
            }
        }
    }

    int main(){
      int testNum;
      cin >> testNum;

      while(testNum--){
        solve();
      }
    }

Can anyone help me understand what is going wrong here?

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
4 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

unordered map is... well... unordered

there can be more than one pair of solution and it'll output a random one

  • »
    »
    4 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    But here I am checking count through unordered map. So for '2' in testcase count is 1 Hence 2,2 should not come and its not coming in my machine also.

    • »
      »
      »
      4 часа назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      It is coming from else part IMO

      • »
        »
        »
        »
        4 часа назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        That part should give same wrong output on all machines right? Is there any possibility of unordered map having memory mix up issue in codeforces in case of multiple test cases?

        • »
          »
          »
          »
          »
          4 часа назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          It is captured in previous comment unordered map is... well... unordered

          • »
            »
            »
            »
            »
            »
            4 часа назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Thanks. Using ordered map has solved my problem. But I still have the doubt why unordered map is giving issue.

»
4 часа назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I had the same problem using sets in python, I only change Pypy to Python compiler and got accepted, so weird lmao

Pypy WA: 291981466

Python 3.10 AC: 291983507

»
4 часа назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I submits the exactly same code and passes: 292088616.

I also invocates the exactly same code for 10+ times and it also gives me correct answer.

I am confused now.

»
3 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I HAVE WRITTEN THE CODE IN JAVA AND USED A DIFFERENT APPROACH BUT ITS GETTING WRONG ANSWER ANYONE COULD SUGGEST THE CHANGE NEEDED PLEASE...

//CODE

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class ii2 {
    
public static void main(String[] args) {
    Scanner sc= new Scanner(System.in);
    int a=sc.nextInt();
    
   
for(int t=0;t<a;t++){
    int n=0,m=0;
    HashMap<Integer,Integer> hm= new HashMap<>();
    int c=sc.nextInt();
    for(int i=0;i<c;i++){
        int cv=sc.nextInt();
        
        if(hm.containsKey(cv)){
            if(n==0&&m==0){
                n=cv;
                m=hm.get(cv);

            }
        }else{
            hm.put((c-2)/cv,cv);
        }

    }System.out.println(n+" "+m);
    
    
}

}
}

THIS GETS THE ANSWER 3 2 FOR LAST TEST OF EXAMPLE TEST CASE BUT IT WASNT ACCEPTED SO PLEASE SUGGEST THE CHANGES NEEDED

  • »
    »
    108 минут назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    note that 3 2 CAN be accepted.

    The problem is you don't ensure $$$c-2$$$ is divisible by $$$cv$$$ when you hm.put((c-2)/cv,cv).