AnestheticCoder's blog

By AnestheticCoder, history, 2 months ago, In English

1598C - Delete Two Elements

137345565

I'm solving 1598C Delete two elements

When I submit the problem I get a wrong answer saying expected was 10 but found 0 but when I copy the same test case and run it in my machine I'm getting 10. I just need help to verify if my logic to solving this question along with my implementation is correct. Please help.

My Solution:-

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <chrono>
#include <cmath>
#include <complex>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define endl "\n"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<vector<ll> > vvl;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef D_DEBUG
  freopen("input.txt", "r", stdin)
#endif
      int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    vector<int> input(n);
    for (int i = 0; i < n; ++i) {
      cin >> input[i];
    }
    ll sum = accumulate(input.begin(), input.end(), 0l);
    ll answer = 0;
    //cout<<sum<<endl;
    unordered_map<int, int> freq;
    if (((2 * sum) % n) == 0) {
      int val = (2 * sum) / n;
      for (int i = 0; i < n; ++i) {
        freq[input[i]]++;
      }
      sort(input.begin(),input.end());
      vector<int>::iterator end = unique(input.begin(), input.end());
      input.resize(distance(input.begin(), end));
      for (int i = 0; i < input.size(); ++i) {
        int first = input[i];
        int second = val - first;
        if(first==second){
            answer += (freq[first]*1ll*(freq[first]-1))/2;
        }
        else {
            answer += freq[first]*freq[second];
        }
        freq[first]=0;
      }
    }
    cout << answer << endl;
  }
}
 
 
 
 
  • Vote: I like it
  • -9
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by AnestheticCoder (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by AnestheticCoder (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a recommendation, don't name your variables first/second. It might cause ambiguous sometimes.I'm not saying that it's the bug btw.

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

in else block

modified1

and

modified2

or even better

ultimate

and submit with 64bit compiler. i guess some where some multiplication is overflowing.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I guess that long is 32-bit on Codeforces so that sum overflows, but on your local machine long is 64-bit so everything is OK.