提出 #68053206


ソースコード 拡げる

#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;
     }
}

提出情報

提出日時
問題 F - Socks 4
ユーザ kadamrohan0215
言語 C++ 20 (gcc 12.2)
得点 0
コード長 4392 Byte
結果 WA
実行時間 148 ms
メモリ 13900 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 525
結果
AC × 1
WA × 1
AC × 4
WA × 23
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
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