結果

問題 No.3617 Swap
コンテスト
ユーザー ルク
提出日時 2026-08-06 16:12:59
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,310 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,407 ms
コンパイル使用メモリ 436,568 KB
実行使用メモリ 186,260 KB
最終ジャッジ日時 2026-08-06 16:13:29
合計ジャッジ時間 19,700 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 3 WA * 1
小課題1 5 % AC * 3
小課題2 5 % AC * 4 TLE * 1
小課題3 15 % AC * 14
小課題4 20 % AC * 14 TLE * 1 -- * 6
小課題5 25 % -- * 8
小課題6 10 % -- * 8
小課題7 20 % AC * 21 WA * 1 TLE * 2 -- * 32
合計 3 * 20% = 60 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vi = vector<int>;
using vvi = vector<vi>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
constexpr ll dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
struct Init {
  Init() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(15);
  }
} init;
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& pair_var) {
  os << "(" << pair_var.first << ", " << pair_var.second << ")";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  os << "[";
  rep(i, vec.size()) {
    os << vec[i];
    if (i != vec.size() - 1) os << ", ";
  }
  os << "]";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& vec) {
  os << "[";
  rep(i, vec.size()) {
    os << vec[i];
    if (i != vec.size() - 1) os << ", ";
  }
  os << "]";
  return os;
}

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
constexpr int BLOCK_SIZE = 500;
vector<vector<int>> cache = {};
vector<pair<int, int>> items;
int getArrM(int x, int idx) {
  vector<int> res = cache[x / BLOCK_SIZE];
  for (int i = x / BLOCK_SIZE * BLOCK_SIZE; i < x; i++) {
    swap(res[items[i].first - 1], res[items[i].second - 1]);
  }
  return res[idx];
};

int main() {
  int n, m, q;
  cin >> n >> m >> q;
  items.resize(m);
  rep(i, m) cin >> items[i].first >> items[i].second;
  vector<int> last(n);
  rep(i, n) last[i] = i;
  rep(i, m) {
    if (i % BLOCK_SIZE == 0) {
      cache.emplace_back(last);
    }
    swap(last[items[i].first - 1], last[items[i].second - 1]);
  }
  vvi db(60, vi(n));
  rep(i, n) db[0][i] = last[i];
  rep(k, 59) {
    rep(i, n) { db[k + 1][i] = db[k][db[k][i]]; }
  }
  rep(i, q) {
    ll t, x;
    cin >> t >> x;
    int rest = t % m;
    int now = (t - rest) / m;
    int pos = getArrM(rest, x - 1);
    rep(i, min(60, (int)logl(t) + 2)) {
      if (now & 1) {
        pos = db[i][pos];
      }
      now >>= 1;
    }
    cout << pos + 1 << endl;
  }
  return 0;
}
0