Approach
Sorting and greedy selection
For Codeforces 266C — Below the Diagonal, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 72 lines of Go from the credited upstream file 266C.go.
- The implementation visibly relies on sequence storage.
- No explicit loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1package main2 3import (4 "bufio"5 "bytes"6 . "fmt"7 "io"8 "sort"9)10 1112 1314type data66 struct {15 a [][]byte16 tp int17 swaps *[][3]int18}19 20func (d data66) Len() int { return len(d.a) }21func (d data66) Less(i, j int) bool {22 if d.tp == 1 {23 return bytes.Count(d.a[i], []byte{1}) < bytes.Count(d.a[j], []byte{1})24 }25 for _, r := range d.a {26 if r[i] > 0 || r[j] > 0 {27 return r[i] > r[j]28 }29 }30 return false31}32func (d data66) Swap(i, j int) {33 if i == j {34 return35 }36 *d.swaps = append(*d.swaps, [3]int{d.tp, i, j})37 if d.tp == 1 {38 d.a[i], d.a[j] = d.a[j], d.a[i]39 } else {40 for _, r := range d.a {41 r[i], r[j] = r[j], r[i]42 }43 }44}45 46func CF266C(_r io.Reader, _w io.Writer) {47 in := bufio.NewReader(_r)48 out := bufio.NewWriter(_w)49 defer out.Flush()50 51 var n, x, y int52 Fscan(in, &n)53 d := data66{make([][]byte, n), 1, &[][3]int{}}54 for i := range d.a {55 d.a[i] = make([]byte, n)56 }57 for i := 1; i < n; i++ {58 Fscan(in, &x, &y)59 d.a[x-1][y-1] = 160 }61 sort.Sort(d)62 d.tp = 263 sort.Sort(d)64 a := *d.swaps65 Fprintln(out, len(a))66 for _, p := range a {67 Fprintln(out, p[0], p[1]+1, p[2]+1)68 }69}70 7172