Submission #68053206


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
static const auto fast = []()
     {ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); return 0;} ();

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename num_t>
using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;  // find_by_order(*) , order_of_key


//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------//
#define mod 1000000007
#define mod2 998244353
#define INF  1e18
//counting number of set bits
#define bitsi(n) __builtin_popcount(n)
#define bitsl(n) __builtin_popcount(n)
#define bitsll(n) __builtin_popcountll(n)
#define endl "\n" 
#define f first
#define s second
#define rep(i,begin,end) for(__typeof(end) i=(begin)-((begin)>(end));i!=(end)-((begin)>(end)); i+=1-2*((begin)>(end)))
#define pb push_back
#define read(a,n) for(ll i=0;i<n;i++){cin>>a[i];}
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
//string to int stoi(s) to long long int stoll(s)
typedef long long ll;
typedef long  double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ull, ull> puu;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#ifndef ONLINE_JUDGE
#include "dbg.cpp"
#else
#define debug(...)
#define debugArr(arr, n)
#endif

//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------//
ll binexp(ll a, ll x, ll m) {
     ll ans = 1;
     a %= m;
     while (x) {
          if (x & 1) { ans = (ans * a) % m; }
          a = (a * a) % m;
          x >>= 1;
     }
     return ans;
}
//return {x,y,gcd} ; a*x + b*y = gcd
void extendgcd(ll a, ll b, ll* v) { if (b == 0) { v[0] = 1; v[1] = 0; v[2] = a; return; } extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return; } //pass an arry of size1 3

ll mod_inverse(ll b, ll m) { return binexp(b, m - 2, m); }
ll mod_add(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a + b) % m) + m) % m; }
ll mod_mul(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a * b) % m) + m) % m; }
ll mod_sub(ll a, ll b, ll m) { a = a % m; b = b % m; return (((a - b) % m) + m) % m; }
ll mod_div(ll a, ll b, ll m) { a = a % m; b = b % m; return (mod_mul(a, mod_inverse(b, m), m) + m) % m; }  //only for prime m

void sieveOfEratosthenes(int n) {
     vector<bool> primes(n + 1, 1);
     primes[0] = 0; primes[1] = 0;
     for (int i = 2;i * i <= n;i++) {
          if (primes[i] == 1) {
               for (int j = i * i;j <= n;j += i) {
                    primes[j] = 0;
               }
          }
     }
}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------//,


void solve() {


}
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------//
int main() {
     ll n, k; cin >> n >> k;
     vll a(n);
     ll total = 0;
     vpll b;
     for (int i = 0; i < n; i++) {
          cin >> a[i];
          total = total + a[i];
          b.pb({ a[i], i });
     }
     sort(all(b));

     ll lt = total;
     ll gt = 0;
     for (int i = n - 1; i >= 0; i--) {
          auto [val, ind] = b[i];
          lt = lt - val;
          // e = 1 + lt / tot-1 * e + gt
          ll x = mod_div(lt, total - 1, mod2);
          x = mod_sub(1, x, mod2);
          x = mod_div((1 + gt) % mod2, x, mod2);
          if (ind == k - 1) {
               cout << x << endl;
               return 0;
          }
          gt = (gt + (x * mod_div(val, total - 1, mod2)) % mod2) % mod2;
     }
}

Submission Info

Submission Time
Task F - Socks 4
User kadamrohan0215
Language C++ 20 (gcc 12.2)
Score 0
Code Size 4392 Byte
Status WA
Exec Time 148 ms
Memory 13900 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 525
Status
AC × 1
WA × 1
AC × 4
WA × 23
Set Name Test Cases
Sample sample00.txt, sample01.txt
All sample00.txt, sample01.txt, testcase00.txt, testcase01.txt, testcase02.txt, testcase03.txt, testcase04.txt, testcase05.txt, testcase06.txt, testcase07.txt, testcase08.txt, testcase09.txt, testcase10.txt, testcase11.txt, testcase12.txt, testcase13.txt, testcase14.txt, testcase15.txt, testcase16.txt, testcase17.txt, testcase18.txt, testcase19.txt, testcase20.txt, testcase21.txt, testcase22.txt, testcase23.txt, testcase24.txt
Case Name Status Exec Time Memory
sample00.txt AC 1 ms 3408 KiB
sample01.txt WA 1 ms 3404 KiB
testcase00.txt AC 1 ms 3420 KiB
testcase01.txt AC 1 ms 3456 KiB
testcase02.txt AC 1 ms 3420 KiB
testcase03.txt WA 32 ms 9208 KiB
testcase04.txt WA 28 ms 13824 KiB
testcase05.txt WA 38 ms 13764 KiB
testcase06.txt WA 84 ms 13784 KiB
testcase07.txt WA 64 ms 8564 KiB
testcase08.txt WA 105 ms 13728 KiB
testcase09.txt WA 42 ms 6096 KiB
testcase10.txt WA 148 ms 13728 KiB
testcase11.txt WA 36 ms 8956 KiB
testcase12.txt WA 116 ms 13776 KiB
testcase13.txt WA 49 ms 8604 KiB
testcase14.txt WA 68 ms 13772 KiB
testcase15.txt WA 62 ms 8332 KiB
testcase16.txt WA 61 ms 13656 KiB
testcase17.txt WA 22 ms 6220 KiB
testcase18.txt WA 143 ms 13884 KiB
testcase19.txt WA 88 ms 13900 KiB
testcase20.txt WA 1 ms 3476 KiB
testcase21.txt WA 86 ms 13788 KiB
testcase22.txt WA 89 ms 13776 KiB
testcase23.txt WA 1 ms 3468 KiB
testcase24.txt WA 82 ms 13804 KiB